Inorder Successor in a Binary Search Tree

Previous
Next

In this post, we will see how to find Inorder Successor in a Binary Search Tree.


Problem

Given a Binary Search Tree and a target node value. Find the Inorder successor of the given node value in the Binary Search tree given. Inorder successor of any node ‘x’ is basically the node which gets traversed immediately after ‘x’ in the Inorder traversal of a tree.
Also assume that the node can not be the rightmost node of the given BST as no Inorder successor can exist for such node as this would be the last node to get traversed in the Inorder traversal.

Inorder successor BST
Inorder successor of 6 is 7 in this Binary Search Tree.


Solution

APPROACH – I :

A basic approach for finding inorder successor of any node in BST can be inspired by the fact that Inorder traversal of any Binary Search tree is sorted which means that Inorder successor of any node ‘x’ is the node having value greater than ‘x’ while being the smallest among all of these nodes having value greater than ‘x’

Let’s call this node as ‘next greater node’ which is actually the Inorder successor.
Now the problem boils down to finding this next greater node having value just greater than given target node.

So, for this, a simple preorder traversal would be enough, where at every node, we compare the node value with the target node and update our final answer if this current node has value greater than target node and lesser than final answer till now.

Time Complexity Discussion :
As we clearly need atleast a complete preorder or any traversal of the given Binary Search tree to explore all the nodes, hence, the worst time complexity of this approach for finding Inorder successor is O(n).

Approach – II:

We know that Inorder successor of any element cannot lie in its left subtree as the Inorder successor of any node will definitely be greater than the target node and it is a property of binary tree that no smaller value node can lie in the left subtree of any node.

Therefore, If a node has a right child, then its inorder successor should definitely be in the right subtree of that node.
Now, there can be two possibilities :
(i) If the target node has a right child :
As we know, inorder successor of any node is the next greater node in a Binary Search tree and next greater node of any node is the leftmost node in the right subtree of that node. In simpler terms, next greater node of any node ‘x’ must be the smallest node among all the nodes having value greater than ‘x’ and we know, right subtree in a Binary Search tree contains all the greater nodes. Now, smallest node among all these greater nodes will be leftmost node. Hence, If the target node has a right child then, its Inorder successor will be leftmost node in its right subtree.

(ii) If the target node does not have a right child :

Now, as there is no Right subtree belonging to the target node, therefore, now we need to find the next greater node in a traversal starting from root, but since we have a Binary search tree to work with hence we can find the next greater node efficiently.
How?
We always start the traversal from root node and compare the value of current node with the target node whose inorder successor has to be found and
-> if it is greater than target node value, then update the final answer and move to the left subtree, WHY? because there is no benefit in going to right subtree as we will only find nodes with values greater than this current node, and as this node itself is greater than target node, this means it can be a potential ‘next greater node’ but nodes in its right subtree can certainly not.
-> if the current node is smaller than the target node, then move to the right subtree as we are looking for nodes having value greater than value of target node.

Time Complexity Discussion :
Functions in both the cases (node with and without right child) traverse the tree in a linear path, that is, at every level we are either going to left subtree or the right subtree which makes the worst time complexity of this approach to O(height) and height of a tree is O(log n), where ‘n’ is the number of nodes.

When you run above program, you will get below output:

6

That’s all about Inorder Successor in a Binary Search Tree.

Previous
Next

Add Comment