Binary Search Tree – In Order Successor Node – Interview Question

Binary Search Tree – In Order Successor Node – Interview Question

June 5, 2020 Uncategorized 0


Given a node in a Binary Search Tree, find the next node as per in order traversal.

Let’s find out how to answer this question in a technical interview.

To begin with, let’s cover real quick what is a binary search tree?

A binary search tree is a binary tree data structure with three main properties:
i) The left subtree of a node contains only nodes with values lesser than the node’s value
ii) The right subtree of a node contains only nodes with values greater than the node’s value
iii) The left and right subtree each must also be a binary search tree.

 

 

Next thing to know there are three ways in which you can traverse a Binary Search tree:

Pre-order – In this algorithm, we traverse the tree in this order: Node, Left child, Right child. So for the given tree we will traverse the nodes as: 8,3,1,6,4,7,10,14,13

In-Order – In this algorithm, we traverse the tree in this order: Left child, Node, Right child. So for the given tree we will traverse the nodes as: 1,3,4,6,7,8,10,13,14

Post-Order – In this algorithm, we traverse the tree in this order: Left, Right, Node. So for the given tree we will traverse the nodes as: 1,4,7,6,3,13,14,10,8

Now let’s come back to the question that we are discussing:

Write the algorithm for finding the next in order successor node of a given node in a binary search tree where each node has a link to its parent.

As per the question, you will be given a node, say: 3 and you have to find the next node as per the in order traversal algorithm. You are not provided the root node directly.
In this Binary search tree for 3, the next node will be the leftmost node of the right subtree. That’s simple, right.
If a node has a right subtree then the answer will simply be the leftmost child of the right subtree.

Next, if the node doesn’t have a right subtree.

For e.g. 4. If the node doesn’t have a right subtree, then we go to the parent. Let’s call the node as n and parent as p. From the parent, we check if we came from the right child or left child. So if n was the left child of p, then the answer is p.

Let’s take a look at the scenario if n was the right child of p. For e.g. 7. In that case, you keep going up until you find a node such that the previous node was a left child and the node itself has a right child. So you go from 7 to 6, 7 was the right child. Then you go from 6 to 3, again 6 was a right child. Then you go from 3 to 8. This time 3 was left child. So as per in order traversal: left – node – right, the next node should be 8.

Lastly, if suppose you get 14, we follow the same algorithm. Since 14 doesn’t have any children. So go up. We go to 10 and see that 14 is the right child of 10. Then we go to 8 and we see that 10 was the right child of 8. Then 8 doesn’t have a parent, so that means there is no successor to 14. 14 is the last node to be traversed in the tree.

Now, if you were to code it.
Let’s first look at the Node class:

class Node
{
public Node left {get; set; }
public Node right {get; set; }
public Node parent {get; set; }
public int value { get; set; }
}

And this is how the method to get the In Order Successor will look like:
Node GetInOrderSuccessor(Node input)
{
if (input == null)
return null;
if (input.right != null)
{
return LeftMostChild(input.right);
}
else
{
Node node = input;
Node parent = input.parent;
if (parent == null || parent.left == node)
return parent;
while (parent != null && parent.left != node)
{
node = parent;
parent = parent.parent;
}
return parent;
}
}

Here is the GitHub Link to the full working solution. I will highly recommend you guys to try it on your own before looking at the solution.
Hope you guys liked the video. I will be adding more such interview questions to the Youtube channel, so do not forget to subscribe. Until next time, happy coding 🙂