What is Inorder Successor in Binary Search Tree?

In a Binary Search Tree, the Inorder Successor of a given node is defined as the node with the smallest value greater than the value of the given node.

It can also be defined as the node next to the current node in the Inorder Traversal of the tree, as inorder traversal of BST returns the nodes in ascending order of their values. Inorder Successor for the last node is NULL.

Example

In the above diagram, inorder successor of 8 is 10, inorder successor of 10 is 11 and inorder successor of 20 is 25.

Where to Find the Inorder Successor?

• If a node has a right child, its successor is the node with the least value present in its right sub-tree. The traversal proceeds towards the right sub-tree of the given node, and the minimum value is present in the leftmost descendant.
• If the given node does not have a right child, its in-order successor is located above it in the tree. While unfolding the recursive calls, the in-order traversal first visits the node whose left child was the most recent input. So, the successor of the given node is the parent of the node's youngest ancestor which is a left child.

How to Find the Inorder Successor in Binary Search Tree?

Method 1 (Uses Parent Pointer)

Algorithm

• Step 1 - Assume that every node has a parent pointer.
• Step 2 - Check the right subtree of input node.
  • If right subtree of node exists, then successor (succ) lies in right subtree. The node with minimum key value in the right subtree is returned.
  • If the node does not contain a right subtree the successor (succ) is one of the ancestors. The parent pointer is used to travel up until a node is found which is the left child of its parent. The parent of such a node is the successor.

Code Implementation C++

Java

Python

Output

Time complexity The time complexity for this approach is O(h), where h is the number of nodes in the Binary Search Tree (or the number of elements in the array).

Space complexity The space complexity for this approach will be O(1) since no extra space is required.

Method 2 (Search from root)

Algorithm

• Step 1 - No parent pointer is involved in this approach.
• Step 2 - Check the right subtree of the input node.
  • If the right subtree of the node exists, then the successor (succ) lies in the right subtree. The node with minimum key value in the right subtree is returned.
  • If the node does not contain a right subtree a search-like technique is implemented to travel down the tree from the root. Move towards the right if the value of a current node is greater than the root’s data, else move towards the left.

Code Implementation C++

Java

Python

Output

Time Complexity The time complexity for this approach is O(h), where h is the number of nodes in the Binary Search Tree (or the number of elements in the array).

Space Complexity The space complexity for this approach will be O(1) since no extra space is required.

Method 3 (Recursive Approach)

Algorithm

• Step 1 - At the initial step, the given node is searched in the tree and the successor is updated to the current node before visiting its left subtree.
• Step 2 - If a node with the desired value is found in the BST, the least value node in its right subtree is returned.
• Step 3 - In case, the node does not have a right subtree, the inorder successor is found in one of its ancestors using recursion.

Code Implementation C++

Java

Python

Output

Time complexity The time complexity for the recursive approach is O(h), where h is the number of nodes in the Binary Search Tree (or the number of elements in the array). In the worst case, the entire tree of height (h) needs to be traversed.

Space complexity The space complexity for this approach will be O(1) since no extra space is required.

Method 4 (Iterative Approach)

Algorithm

• Step 1 - At the initial step, the given node is searched in the tree and the successor is updated to the current node before visiting its left subtree.
• Step 2 - If a node with the desired value is found in the BST, the least value node in its right subtree is returned.
• Step 3 - In case, the node does not have a right subtree, the inorder successor is found in one of its ancestors using iteration.

Code Implementation C++

Java

Python

Output

Time Complexity The time complexity for the iterative approach is O(h), where h is the number of nodes in the Binary Search Tree (or the number of elements in the array). In the worst case, the entire tree of height (h) needs to be traversed.

Space Complexity The space complexity for this approach will be O(1), since no extra space is required.

Learn more

• Binary Search Tree
• Tree Traversal in Data Structure