BST Inorder Successor in DSA Java - Execution Trace

Concept Flow - BST Inorder Successor

Start at root

↓

Search for target node

↓

Found target node?

No→Return null

Yes↓

Does target have right child?

Yes→Go to right child

↓

Go left as far as possible

↓

Leftmost node is successor

No↓

Go up to ancestor where target is in left subtree

↓

That ancestor is successor

↓

Return successor

Find the node's inorder successor by checking right subtree or ancestors.

Execution Sample

DSA Java

Node inorderSuccessor(Node root, Node target) {
  if (target.right != null) {
    return leftmost(target.right);
  }
  Node successor = null;
  Node ancestor = root;
  while (ancestor != target) {
    if (target.val < ancestor.val) {
      successor = ancestor;
      ancestor = ancestor.left;
    } else {
      ancestor = ancestor.right;
    }
  }
  return successor;
}

Finds the inorder successor of a target node in a BST.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start at root	50	successor=null, ancestor=50	50 / \ 30 70
2	Compare target(65) with ancestor(50)	50	target.val > ancestor.val, move ancestor right	50 / \ 30 70
3	Move ancestor to right child	70	ancestor=70	50 / \ 30 70
4	Compare target(65) with ancestor(70)	70	target.val < ancestor.val, successor=70, move ancestor left	50 / \ 30 70
5	Move ancestor to left child	60	ancestor=60, successor=70	50 / \ 30 70 / 60
6	Compare target(65) with ancestor(60)	60	target.val > ancestor.val, move ancestor right	50 / \ 30 70 / 60
7	Move ancestor to right child	65	ancestor=65	50 / \ 30 70 / 60 \ 65
8	Ancestor is target? Yes, loop ends	65	exit loop	50 / \ 30 70 / 60 \ 65
9	Return successor	70	successor=70	50 / \ 30 70 / 60 \ 65

💡 Ancestor reached target, loop ends; successor is 70

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 5	After Step 6	After Step 7	Final
successor	null	null	70	70	70	70	70
ancestor	50	70	70	60	60	65	65

Key Moments - 3 Insights

Why do we check if the target node has a right child first?

Because if the target has a right child, its inorder successor is the leftmost node in that right subtree (see execution_table step 1). This is a direct shortcut.

Why do we update the successor when moving left in the ancestor path?

When moving left, the ancestor node is greater than the target and could be the next bigger node, so we save it as a potential successor (see execution_table step 4).

What happens if the target node has no right child and no ancestor on the left path?

Then the successor is null, meaning the target is the largest node in the BST and has no inorder successor (not shown in this example but implied by exit conditions).

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'successor' after step 4?

A null

B 70

C 60

D 50

💡 Hint

Check the 'Pointer Changes' column at step 4 where successor is updated.

At which step does the ancestor pointer reach the target, ending the loop?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the 'Current Node' column to find when ancestor is 65.

If the target node had a right child, which step would handle finding the successor?

A Step 1

B Step 3

C Step 5

D Step 9

💡 Hint

Refer to the concept_flow where right child presence leads to leftmost node search immediately.

Concept Snapshot

BST Inorder Successor:
- If target has right child, successor is leftmost node in right subtree.
- Else, successor is nearest ancestor for which target is in left subtree.
- Traverse from root to target, updating successor when moving left.
- Return successor or null if none.
- Useful for next bigger element in BST traversal.

Full Transcript

To find the inorder successor of a node in a BST, first check if the node has a right child. If yes, the successor is the leftmost node in that right subtree. If no right child exists, start from the root and move down to the target node. While moving, whenever you go left, update the successor to the current ancestor because it might be the next bigger node. When you reach the target, the last updated successor is the inorder successor. If no successor is found, it means the target is the largest node. This method efficiently finds the next bigger node in BST order.

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