Find Inorder Successor in BST

102.Inorder Successor in a Binary Search Tree

Tree

Binary Search

Problem Statement:

Given the root of a binary search tree (BST) and a node p in it, find the inorder successor of that node in the BST. The successor of a node p is the node with the smallest key greater than p.val.

Algorithm:

1. If node p has a right child:
   • The successor is the leftmost node in the right subtree of p.
2. If node p does not have a right child:
   • Use the BST property and start from the root to find the successor:
     • If p.val is less than the current root's value, update the successor to the current root and move to the left subtree.
     • Otherwise, move to the right subtree.
3. Return the stored successor.

Complexity:

Time: O(h), where h is the height of the tree | Space: O(1).

Java Implementation:

public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        // Case 1: p has a right child
        if (p.right != null) {
            p = p.right;
            while (p.left != null) 
                p = p.left;
            return p;
        }

        // Case 2: p does not have a right child
        TreeNode successor = null;
        while (root != null) {
            if (p.val < root.val) {
                successor = root; // Update successor
                root = root.left; // Move to the left subtree
            } else {
                root = root.right; // Move to the right subtree
            }
        }

        return successor;
    }
}
                

Python Implementation:

class Solution:
    def inorderSuccessor(self, root, p):
        # Case 1: p has a right child
        if p.right:
            p = p.right
            while p.left:
                p = p.left
            return p

        # Case 2: p does not have a right child
        successor = None
        while root:
            if p.val < root.val:
                successor = root # Update successor
                root = root.left # Move to the left subtree
            else:
                root = root.right # Move to the right subtree

        return successor
                

C++ Implementation:

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        // Case 1: p has a right child
        if (p->right) {
            p = p->right;
            while (p->left) 
                p = p->left;
            return p;
        }

        // Case 2: p does not have a right child
        TreeNode* successor = nullptr;
        while (root) {
            if (p->val < root->val) {
                successor = root; // Update successor
                root = root->left; // Move to the left subtree
            } else {
                root = root->right; // Move to the right subtree
            }
        }

        return successor;
    }
};