Inorder Successor In Bst - Leetcode Solution

Problem Statement:

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

The in-order successor is the node that comes after the given node in the in-order traversal.

Solution:

In a binary search tree, the left subtree of a node contains only nodes with values less than the node. Similarly, the right subtree of a node contains only nodes with values greater than the node. Therefore, we can leverage this property to find the in-order successor of a node in a BST.

If the node has a right child, then the in-order successor is the leftmost node in the right subtree of the node. If the node does not have a right child, then the in-order successor is the lowest ancestor of the node whose left child is also an ancestor of the given node.

Let’s see an algorithm to find the in-order successor of a given node in a BST.

1. Start from the root of the BST.
2. If the root is null, return null.
3. If the given node is less than or equal to the root, recurse on the left subtree.
4. If the given node is greater than the root, recurse on the right subtree.
5. If the given node is found, perform the following steps:
   • If the node has a right child, return the leftmost node in the right subtree.
   • If the node does not have a right child, trace back to the root using the parent pointer until you reach a node with a left child lower than the given node. Return that node.

Let’s implement the above algorithm in code:

public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    if (root == null)
        return null;

    if (p.val >= root.val) {
        return inorderSuccessor(root.right, p);
    } else {
        TreeNode left = inorderSuccessor(root.left, p);
        return (left != null) ? left : root;
    }
}

In the code above, we first check if the root is null. If yes, we return null. If not, we check if the given node is less than or equal to the root. If yes, we recurse on the left subtree. If not, we recurse on the right subtree. We repeat this process until we find the given node.

Once we find the given node, we again check if it has a right child. If yes, we return the leftmost node in the right subtree. If not, we trace back to the root using the parent pointer until we reach a node with a left child lower than the given node. We then return that node, which is the in-order successor of the given node.

Conclusion:

In this post, we have discussed how to find the in-order successor of a node in a binary search tree. We have presented an algorithm and the corresponding code to implement the algorithm in Java.

1