Solution: Inorder Successor in BST

Let’s solve the Inorder Successor in BST problem using the Tree Depth-First Search pattern.

We'll cover the following

Statement

You are given the root node of a binary search tree and a specific node p. Your task is to return the inorder successor of this p node. If there is no inorder successor of the given node, return NULL.

Note: The inorder successor of p is the node with the smallest value greater than p.data in the binary search tree.

Constraints:

  • The tree contains nodes in the range [1,500][1,500].

  • −104≤-10^4 \leqNode.data ≤104\leq 10^4

  • All Nodes will have unique values.

  • p should exist in the tree.

Solution

To solve this problem, we will use the depth-first search pattern because it allows us to perform an inorder traversal of the tree, which is necessary to find the inorder successor of a given node.

The properties of the BST allow us to make an efficient search by discarding half of the tree at each step. We start from the root node and compare the value of the current node with p. It helps us decide whether to move to the left or right subtree. If p is greater than or equal to the current node’s value, we move to the right subtree, as the in-order successor must be in the right subtree or above the current node. Otherwise, we explore the left subtree to find a potentially smaller successor. This way, we efficiently find the inorder successor of the given node.

Let’s go through the algorithm to see how we will reach the solution:

  • Initialize a variable successor to NULL. It stores the potential inorder successor as we traverse the tree.

  • Traverse the tree starting from the root, and for each node, compare the values of p and root:

    • If the value of p is greater than or equal to the value of the root, the inorder successor must be in the right subtree or higher up in the tree. We move to the right subtree by setting root = root.right.

    • Otherwise, we update the successor to the current node, as this node is a potential in-order successor. Then, move to the left subtree by setting root = root.left.

  • After the loop ends, we return the successor. This contains the inoder successor of the given node.

Note: If there was no in-order successor of the given node, the successor will remain NULL.

Let’s look at the following illustration to get a better understanding of the solution:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.