BST Inorder Successor in DSA Java

Mental Model

The inorder successor of a node in a BST is the next node in sorted order. It is the smallest node greater than the given node.

Analogy: Imagine a line of people sorted by height. The inorder successor is the person just taller than you standing right after you in line.

       5
      / \
     3   7
    / \   \
   2   4   8

Node: 4 ↑
Inorder successor: 5

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, find inorder successor of node 4

Goal: Find the node that comes immediately after 4 in sorted order

Step 1: Check if node 4 has right subtree

Node 4 has no right child

Why: If right subtree exists, successor is leftmost node there; else, go up ancestors

Step 2: Move up to parent 3, since 4 > 3, keep moving up

Current ancestor: 3

Why: Successor must be ancestor greater than node

Step 3: Move up to parent 5, 5 > 4, so successor found

Current ancestor: 5 ↑ successor

Why: First ancestor greater than node is inorder successor

Result:

Inorder successor of 4 is 5

Annotated Code

DSA Java

class Node {
    int val;
    Node left, right, parent;
    Node(int val) {
        this.val = val;
        this.left = this.right = this.parent = null;
    }
}

public class BSTInorderSuccessor {

    // Find leftmost child in subtree
    private static Node leftmost(Node node) {
        while (node.left != null) {
            node = node.left; // go left to find smallest
        }
        return node;
    }

    // Find inorder successor of given node
    public static Node inorderSuccessor(Node node) {
        if (node == null) return null;

        // Case 1: right subtree exists
        if (node.right != null) {
            return leftmost(node.right); // successor is leftmost in right subtree
        }

        // Case 2: no right subtree, go up to find ancestor
        Node curr = node;
        Node p = curr.parent;
        while (p != null && curr == p.right) {
            curr = p; // move up
            p = p.parent; // move up
        }
        return p; // first ancestor where node is in left subtree
    }

    // Build example tree and test
    public static void main(String[] args) {
        Node root = new Node(5);
        Node n3 = new Node(3);
        Node n7 = new Node(7);
        Node n2 = new Node(2);
        Node n4 = new Node(4);
        Node n8 = new Node(8);

        root.left = n3; n3.parent = root;
        root.right = n7; n7.parent = root;
        n3.left = n2; n2.parent = n3;
        n3.right = n4; n4.parent = n3;
        n7.right = n8; n8.parent = n7;

        Node succ = inorderSuccessor(n4);
        if (succ != null) {
            System.out.println("Inorder successor of " + n4.val + " is " + succ.val);
        } else {
            System.out.println("No inorder successor for " + n4.val);
        }
    }
}

while (node.left != null) { node = node.left; // go left to find smallest }

Find leftmost node in right subtree to get successor

if (node.right != null) { return leftmost(node.right); // successor is leftmost in right subtree }

If right subtree exists, successor is leftmost node there

while (p != null && curr == p.right) { curr = p; // move up p = p.parent; // move up }

Move up ancestors until node is left child, then parent is successor

Output

Inorder successor of 4 is 5

Complexity Analysis

Time: O(h) because we traverse up or down the tree height h at most once

Space: O(1) because no extra space besides pointers is used

vs Alternative: Naive approach would do inorder traversal O(n) and find successor, which is slower than O(h)

Edge Cases

Node has right subtree

Successor is leftmost node in right subtree

DSA Java

if (node.right != null) {
    return leftmost(node.right);

Node is the maximum node (no successor)

Returns null indicating no successor

DSA Java

while (p != null && curr == p.right) {
    curr = p;
    p = p.parent;
}

Node is null

Returns null safely

DSA Java

if (node == null) return null;

When to Use This Pattern

When asked for the next bigger element in a BST, use inorder successor logic because it finds the next node in sorted order efficiently.

Common Mistakes

Mistake: Not handling the case when node has no right subtree and needing to move up ancestors
Fix: Add loop to move up parents until node is left child of parent

Mistake: Assuming successor is always right child
Fix: Check if right subtree exists; if not, go up ancestors

Summary

Finds the next node in sorted order after a given node in a BST.

Use when you need the immediate larger value than a given node in BST.

If right subtree exists, successor is leftmost there; else, move up ancestors until node is left child.

Practice

1. What is the inorder successor of a node in a Binary Search Tree (BST)?

easy

A. The node with the smallest key greater than the given node's key

B. The node with the largest key smaller than the given node's key

C. The root node of the BST

D. The left child of the given node

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits nodes in ascending order of their keys in a BST.

2. Step 2: Define inorder successor

   The inorder successor of a node is the next node visited after it in inorder traversal, which is the smallest node greater than it.

3. Final Answer:

   The node with the smallest key greater than the given node's key -> Option A

4. Quick Check:

   Inorder successor = smallest greater key [OK]

Hint: Inorder successor is next bigger node in sorted order [OK]

Common Mistakes:

• Confusing successor with predecessor
• Thinking successor is always right child
• Assuming successor is parent node

2. Which of the following Java method signatures correctly represents a function to find the inorder successor in a BST node class?

easy

A. public void inorderSuccessor(Node p)

B. public Node inorderSuccessor(Node root, Node p)

C. public int inorderSuccessor(Node root)

D. public Node inorderSuccessor(int key)

Solution

1. Step 1: Identify required inputs and outputs

   To find inorder successor, we need the BST root and the target node; output is the successor node.

2. Step 2: Match method signature

   public Node inorderSuccessor(Node root, Node p) takes root and node, returns Node, matching requirements.

3. Final Answer:

   public Node inorderSuccessor(Node root, Node p) -> Option B

4. Quick Check:

   Input root and node, output node [OK]

Hint: Method needs root and target node, returns successor node [OK]

Common Mistakes:

• Missing root parameter
• Returning int instead of Node
• Using void return type

3. Given the BST below and the node with value 15, what is the inorder successor?

       20
      /  \
    10    30
      \
      15

medium

A. 20

B. 15

C. 30

D. 10

Solution

1. Step 1: Locate node 15 and check right subtree

   Node 15 has no right child, so successor is ancestor with greater value.

2. Step 2: Find lowest ancestor greater than 15

   Ancestor 20 is the next bigger node after 15.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Next bigger after 15 is 20 [OK]

Hint: If no right child, successor is nearest bigger ancestor [OK]

Common Mistakes:

• Choosing 30 which is too big
• Choosing 10 which is smaller
• Choosing the node itself

4. Consider this buggy Java code snippet to find the inorder successor of a node in BST:

public Node inorderSuccessor(Node root, Node p) {
    if (p.right != null) {
        Node curr = p.right;
        while (curr.left != null) {
            curr = curr.left;
        }
        return curr;
    }
    Node succ = null;
    while (root != null) {
        if (p.val < root.val) {
            succ = root;
            root = root.left;
        } else {
            root = root.right;
        }
    }
    return succ;
}

What is the main bug in this code?

medium

A. It uses wrong comparison operator in while loop

B. It incorrectly updates successor when p.val >= root.val

C. It does not handle the case when p has no right child

D. It may return null even if successor exists

Solution

1. Step 1: Analyze right subtree handling

   If p has right child, code correctly finds leftmost node in right subtree.

2. Step 2: Analyze ancestor search loop

   Loop updates successor when p.val < root.val, else moves right. This is correct logic.

3. Step 3: Identify potential null return

   If p is the largest node, no successor exists, so null return is valid. Otherwise, code works.

4. Final Answer:

   It may return null even if successor exists -> Option D

5. Quick Check:

   Null return possible if logic misses successor [OK]

Hint: Check if successor can be missed when traversing ancestors [OK]

Common Mistakes:

• Assuming null means no successor always
• Ignoring right subtree case
• Misreading comparison operators

5. You have a BST and want to find the inorder successor of node with value 25. The BST is:

        40
       /  \
     20    60
    /  \  /  \
  10  30 50  70
       \
       25

Which node is the inorder successor of 25 and why?

hard

A. 30, because it is the smallest node greater than 25 in the right subtree

B. 50, because it is the leftmost node in the right subtree of 25

C. 40, because 25 has no right child and 40 is the nearest bigger ancestor

D. 20, because it is the parent of 25

Solution

1. Step 1: Check if node 25 has right child

   Node 25 has no right child, so successor is ancestor or next bigger node.

2. Step 2: Find nearest ancestor greater than 25

   Node 40 is the nearest ancestor greater than 25, so it is the inorder successor.

3. Final Answer:

   40, because 25 has no right child and 40 is the nearest bigger ancestor -> Option C

4. Quick Check:

   Next bigger node after 25 is 40 [OK]

Hint: Successor is leftmost node in right subtree or nearest bigger ancestor [OK]

Common Mistakes:

• Choosing 30 which is smaller than 25
• Choosing 50 which is too far
• Choosing parent 20 which is smaller