Find In order successor II [parent pointer]

XXX. Find Inorder Successor in BST (Parent Pointer)

Tree

BST

Problem Statement:

Given a node in a Binary Search Tree with parent pointers, find its inorder successor (the next node in inorder traversal).

• Each node has parent pointer
• No access to tree root
• Return null if no successor exists

Implementation:

// Successor but now we only have parent link and we don't get the root
// Extremely easy and you should know this solution at the top of your head

// Algorithm
// If the node has a right child, and hence its successor is somewhere lower in the tree. 
// Go to the right once and then as many times to the left as you could. 
// Return the node you end up with.

// Node has no right child, and hence its successor is somewhere upper in the tree. 
// Go up till the node that is left child of its parent. The answer is the parent.

public Node inorderSuccessor(Node x) {
    // the successor is somewhere lower in the right subtree
    if (x.right != null) {
        x = x.right;
        while (x.left != null) x = x.left;
        return x;
    }

    // the successor is somewhere upper in the tree
    while (x.parent != null && x == x.parent.right) x = x.parent;
    return x.parent;
}
                

Complexity:

Time Complexity: O(h), where h is height of tree
Space Complexity: O(1), constant space

Explanation:

• **Case 1: Right Child Exists**:
  • Go to right child once
  • Then go left as far as possible
  • This node is the successor
• **Case 2: No Right Child**:
  • Go up using parent pointers
  • Stop when current node is left child of parent
  • Parent is the successor
• **Key Points**:
  • No need for tree root
  • Parent pointers make upward traversal possible
  • Two distinct cases handle all scenarios