In this blog post, I want to share with you my approach as well as some tips for approaching problems that you have not tried before.
The BST Inorder Successor ProblemIn a Binary Search Tree (BST), an Inorder Successor of a node is defined as the node with the smallest key greater than the key of the input node (see examples below).
Given a node inputNode in a BST, you’re asked to write a function findInOrderSuccessor that returns the Inorder Successor of inputNode.
If inputNode has no Inorder Successor, return null.
— www.
pramp.
comIn this diagram, the inorder successor of 9 is 11 and the inorder successor of 14 is 20.
— PrampThis problem comes set up with a Binary Search Tree already created, as well as the necessary methods and variables.
Click here to visit the code snippet and open it up in another screen so you can follow along with this walkthrough.
Step 1: Break it DownFrom what I have learned throughout my education experience, one of the best ways to approach a problem you do not understand is to break it apart piece by piece.
Oh, and ask PLENTY of questions.
Sure you might not understand what the whole of it means just yet, but you definitely understand some of the parts.
So we will do just that and dissect the unknown parts.
What is a binary search tree?Well I know what binary search is; it is used to find a specific value in a sorted collection of items by reducing the search scope by half until an item is found or not found.
So if that holds true, I know two things:it is used with a sorted collection of itemswe will approach it by reducing the search scope by half on each run, implying a runtime complexity of O(log N)The actual definition is the following:A tree is a a collection of nodes connected by some edges.
A tree is a non linear data structure.
A Binary Search tree is a binary tree in which nodes which have lesser value are stored on the left while the nodes with higher value are stored at the right.
— Geeks for GeeksMy interviewer walked me through the setup of a binary search tree.
He also explained to me that “inorder” is one of three possible tree traversals (the other two being preorder and postorder).
The constructor and necessary methods were already built in the problem, so all I had to understand were the general components:Node: each node acts somewhat like a container with properties, those being key, parent, left, and right.
Root: the root at the very beginning of the tree with no predecessorsKey: the number or value of the nodeParent: the predecessor node of the current node you are referencingLeft and Right: the successor nodes of the current node you are referencing.
In a BST, the left child node’s key is less than the current node key, and the right child node’s key is greater than the current node key.
I also skimmed over each built-in function to understand its purpose:Node(key) : the Node class constructor; defines the properties for each Node instanceBinarySearchTree() : creates a binary search treeBinarySearchTree.
prototype.
insert(key) : builds the Node for a given key, and inserts into the proper location in the BSTBinarySearchTree.
prototype.
getNodeByKey() : finds the respective Node instance for a given keyWhat we have to build:BinarySearchTree.
prototype.
findInOrderSuccessor(inputNode)So to be clear, I only had to build the function that accepts an inputNode and want it to return its inorder successor, which would be the node that has the next-greatest key in this sorted collection.
If it does not exist, it will return null.
The tests starting at line 108 to the end will help to make sure your code works or not.
Step 2: Talk Before You WalkAt this point, I had a vague understanding of the set up of the problem and what it was asking me to do.
Basically, I needed to build a function that would look for a specific value, using binary search.
My interviewer advised that I think of the tree having only the values 9, 20, and 25, and talk through my expectations.
// 20// / // 9 25If inputNode = 9, its inorder successor should be 20.
If inputNode = 20, its inorder successor should be 25.
If inputNode = 25, its inorder successor is null.
I knew that I needed some conditional statements because there was no clear pattern for how to find the inorder successor of inputNode.
Continuing this talk-through with more of the tree, some of our expectations change.
// 20// / // 9 25// / // 5 12CHANGED: If inputNode = 9, its inorder successor should be 12.
SAME: If inputNode = 20, its inorder successor should be 25.
SAME: If inputNode = 25, its inorder successor is null.
New tests:If inputNode = 5, its inorder successor is 9.
If inputNode = 12, its inorder successor is 20.
So, starting with these talk-throughs, we can conclude a couple of patterns and pretty much pseudocode our solution.
If you are coding along, pause here to try to come up with some of your own pseudocode.
When you are done thinking, continue scrolling.
After some analyzing, I came up with the following pseudocode.
I emphasized the words that can be translated into code:If it exists, the right child node is the inorder successor of the inputNode.
If inputNode has no right child node, call its next greatest parent node.
This means finding its parent until we find a node with a key that is greater than the current node’s key.
If the inputNode has no right child node AND its key is greater than that of its parent, it has no inorder successor so it will return null.
Step 3: Put it All TogetherAfter I was confident that I considered a multitude of edge cases, I rationalized that my pseudocode made sense.
I was ready to compose a solution in JavaScript.
I wrote the code out line by line and before running it, I talked it through just as carefully as I had before writing the code.
This methodical approach is transferable to any coding career as it can reduce silly mistakes created by eager typers!Again, if you are coding along, I recommend you try this out first in a Repl or IDE of choice before scrolling down further.
When you are ready, compare your solution to mine below!.As always, my solution is just one of many possible approaches and is in no way the best approach; it is simply what worked for me.
My SolutionConclusionFrom not knowing what a BST even was, to coming up with a solution using a BST, I felt successful after conquering something that seemed very challenging.
I hope that this article helped inspire anyone to try a binary search tree problem for the first time!.I wish the best of luck to you in your technical interviews.
My final takeaways:More often than not, people want to see you succeed.
Coding challenges are called “challenges” for a reason.
Be confident in your ability to approach new problems using your existing knowledge.
If you have time, use it!.Pramp recommended 45 minutes per question.
Ask a lot of questions and repeat the information back to your interviewer to confirm your understanding.
Mentally or verbally talk through your code with smaller test cases before you run it to see if your expectations make sense, and then try developing a coded solution.
And lastly, I owe a BIG shoutout to my Pramp partner match!.Thank you for your help!ResourcesImplementation of Binary Search Tree for Javascript — Geeks For GeeksHow Binary Search Trees Work in JS — Prakash PawarData structures in JS: Binary Search Trees React App — Oliverio Alonso.. More details