Example: Inorder successor for BST - rFronteddu/general_wiki GitHub Wiki

To find the inorder successor of a node in a Binary Search Tree (BST), you need to consider two cases:

• If the right subtree of the given node is not null, then the inorder successor is the leftmost node in the right subtree.
• If the right subtree is null, then you need to backtrack to find the nearest ancestor whose left subtree contains the given node. The inorder successor will be this ancestor. Here's the Java code to find the inorder successor in a BST:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null || p == null) {
            return null;
        }
        
        if (p.right != null) {
            // Case 1: If the right subtree of p is not null, 
            // then the inorder successor is the leftmost node in the right subtree.
            TreeNode successor = p.right;
            while (successor.left != null) {
                successor = successor.left;
            }
            return successor;
        } else {
            // Case 2: If the right subtree of p is null, backtrack to find the nearest ancestor 
            // whose left subtree contains p. The inorder successor will be this ancestor.
            TreeNode successor = null;
            TreeNode current = root;
            while (current != null) {
                if (p.val < current.val) {
                    successor = current;
                    current = current.left;
                } else if (p.val > current.val) {
                    current = current.right;
                } else {
                    break; // Found p
                }
            }
            return successor;
        }
    }
}