BST Inorder Successor in DSA C# - Execution Trace

Concept Flow - BST Inorder Successor

Start at root node

↓

Search for target node

↓

Found target node?

No→Return null (no successor)

Yes↓

Does target have right child?

Yes→Go to right child

↓

Find leftmost node in right subtree

↓

Go up to ancestor where target is in left subtree

↓

Return that ancestor as successor

↓

Done

Find the inorder successor by first locating the target node, then either going to its right subtree's leftmost node or moving up to the nearest ancestor where the target is in the left subtree.

Execution Sample

DSA C#

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;
}

This code finds the inorder successor of a target node in a BST by checking the right subtree or moving up to ancestors.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start at root	20	successor=null, ancestor=20	20 / \ 10 30
2	Compare target(10) with ancestor(20)	20	target.val < ancestor.val → successor=20, ancestor=10	20 / \ 10 30
3	Compare target(10) with ancestor(10)	10	ancestor=10 (target found)	20 / \ 10 30
4	Check if target.right exists	10	target.right=null	20 / \ 10 30
5	Return successor	20	successor=20	20 / \ 10 30
6	End	N/A	Return node with val=20	Successor is 20

💡 Target node found; no right child; successor is nearest ancestor where target is in left subtree

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
successor	null	null	20	20	20	20
ancestor	20	20	10	10	10	10
target	10	10	10	10	10	10

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, as shown in execution_table step 4.

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

When target.val < ancestor.val, the ancestor could be the next bigger node, so we update successor to ancestor (see step 2).

What if the target node has no right child and no ancestor where target is in left subtree?

Then the target node is the largest node, so successor remains null and no successor exists (not shown in this example).

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what happens to the successor variable?

A It remains null

B It is set to 20

C It is set to 10

D It is set to 30

💡 Hint

Check the Pointer Changes column at step 2 in execution_table

At which step does the algorithm find the target node?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look for the step where ancestor equals target in execution_table

If the target node had a right child, which step would change in the execution_table?

A Step 4 would return the leftmost node of right subtree

B Step 2 would update successor to null

C Step 3 would skip finding target

D Step 5 would return null

💡 Hint

Check the Operation and Pointer Changes columns at step 4

Concept Snapshot

BST Inorder Successor:
- If target has right child, successor = leftmost node in right subtree
- Else, successor = nearest ancestor where target is in left subtree
- Traverse from root to target updating successor when moving left
- Return successor or null if none exists

Full Transcript

To find the inorder successor in a BST, start at the root and search for the target node. If the target has a right child, the successor is the leftmost node in that right subtree. Otherwise, move up the tree to find the nearest ancestor where the target is in the left subtree. This ancestor is the successor. If no such ancestor exists, the target has no inorder successor. The code tracks pointers to successor and ancestor while traversing. The execution table shows each step, pointer updates, and the visual state of the BST. Key moments clarify why we check the right child first and how the successor updates when moving left. The visual quiz tests understanding of these steps.

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 key greater than the node's key.

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 C# method signatures correctly represents a function to find the inorder successor of a BST node?

easy

A. public void InorderSuccessor(TreeNode root, TreeNode p)

B. public TreeNode InorderSuccessor(TreeNode root, TreeNode p)

C. public TreeNode FindSuccessor(TreeNode p)

D. public int InorderSuccessor(int root, int p)

Solution

1. Step 1: Check parameter types for BST nodes

   The method should accept the BST root and the target node to find successor, both as TreeNode objects.

2. Step 2: Check return type

   The method returns the successor node, so return type must be TreeNode, not int or void.

3. Final Answer:

   public TreeNode InorderSuccessor(TreeNode root, TreeNode p) -> Option B

4. Quick Check:

   Correct signature uses TreeNode parameters and returns TreeNode [OK]

Hint: Successor method needs root and target node, returns TreeNode [OK]

Common Mistakes:

• Using int instead of TreeNode for parameters
• Returning void instead of TreeNode
• Missing root parameter

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

        20
       /  \
     10    30
       \     \
       15    40

TreeNode successor = InorderSuccessor(root, node15); Console.WriteLine(successor.val);

medium

A. 40

B. 30

C. 20

D. 15

Solution

1. Step 1: Locate node 15 and find its inorder successor

   Node 15 has no right child, so successor is the lowest ancestor whose left child is also ancestor of 15, which is 20.

2. Step 2: Confirm successor value

   20 is the next bigger node after 15 in inorder traversal.

3. Final Answer:

   20 -> Option C

4. Quick Check:

   Successor of 15 is 20 [OK]

Hint: If no right child, go up to first bigger ancestor [OK]

Common Mistakes:

• Choosing right child 30 incorrectly
• Choosing node itself as successor
• Choosing 40 which is too far

4. The following code attempts to find the inorder successor of a node in a BST but returns null incorrectly. What is the bug?

public TreeNode InorderSuccessor(TreeNode root, TreeNode p) {
    if (p.right != null) {
        TreeNode curr = p.right;
        while (curr.left != null) curr = curr.left;
        return curr;
    }
    TreeNode successor = null;
    while (root != null) {
        if (p.val < root.val) {
            successor = root;
            root = root.left;
        } else {
            root = root.right;
        }
    }
    return successor;
}

medium

A. The code does not handle the case when p has no right child

B. The while loop condition should be curr.right instead of curr.left

C. The comparison p.val < root.val should be p.val <= root.val

D. The code is correct and should not return null incorrectly

Solution

1. Step 1: Analyze right subtree handling

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

2. Step 2: Analyze ancestor traversal

   If no right child, code moves up tree to find first ancestor greater than p, correctly updating successor.

3. Step 3: Confirm no logical errors

   Comparisons and loops are correct; code returns null only if no successor exists (p is max node).

4. Final Answer:

   The code is correct and should not return null incorrectly -> Option D

5. Quick Check:

   Code handles both cases correctly [OK]

Hint: Check both right subtree and ancestor paths for successor [OK]

Common Mistakes:

• Changing left to right in while loop incorrectly
• Using <= instead of < causing wrong ancestor selection
• Assuming code misses no-right-child case

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

          40
         /  \
       20    60
      /  \     \
    10   30    70
                 \
                 80

If the node with value 50 does not exist in the tree, what should your inorder successor function return?

hard

A. null, because the node is not in the BST

B. The smallest node greater than 50, which is 60

C. The largest node smaller than 50, which is 40

D. The root node, which is 40

Solution

1. Step 1: Confirm node presence in BST

   Node with value 50 is not present in the BST, so no direct successor can be found.

2. Step 2: Understand successor function behavior

   Successor function requires the node to find its successor; if node not found, function should return null or indicate absence.

3. Final Answer:

   null, because the node is not in the BST -> Option A

4. Quick Check:

   Node missing means no successor found [OK]

Hint: Successor only valid if node exists in BST [OK]

Common Mistakes:

• Returning closest bigger node even if node missing
• Returning root node incorrectly
• Returning predecessor instead of null