BST Inorder Successor in DSA C - Execution Trace

Concept Flow - BST Inorder Successor

Start at root

↓

Search for target node

↓

Found target node?

No→Return None

Yes↓

Does target have right child?

Yes→Go to right child

↓

Go left as far as possible

↓

Go up to ancestor where node is left child

↓

Return this ancestor as successor

↓

Done

Find the node, then if it has right child, successor is leftmost node in right subtree; else go up to ancestor where node is in left subtree.

Execution Sample

DSA C

Node* inorderSuccessor(Node* root, Node* p) {
  if (p->right) {
    p = p->right;
    while (p->left) p = p->left;
    return p;
  }
  Node* succ = NULL;
  while (root) {
    if (p->val < root->val) {
      succ = root;
      root = root->left;
    } else {
      root = root->right;
    }
  }
  return succ;
}

Finds the inorder successor of node p in BST rooted at root.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start at root to find node 5	10	root points to 10	10 / \ 5 15 / \ 2 7 20
2	Go left since 5 < 10	5	root moves to 5	10 / \ 5 15 / \ 2 7 20
3	Found node 5	5	root stays at 5	10 / \ 5 15 / \ 2 7 20
4	Check if node 5 has right child	5	No pointer change	5 has right child 7
5	Go to right child 7	7	p moves to 7	7 (no left child)
6	Go left as far as possible from 7	7	No left child, stop	7
7	Return 7 as successor	7	Return node 7	Successor is 7
8	Example: Find successor of 7 (no right child)	10	Start at root 10	10 / \ 5 15 / \ 2 7 20
9	7 >= 10? No, go left	5	root moves to 5	5 subtree
10	7 >= 5? Yes, go right	7	root moves to 7	7 node found
11	7 has no right child, find ancestor	10	succ = NULL initially	Start ancestor search
12	7 < 10, succ = 10, go left	5	succ updated to 10	Ancestor candidate 10
13	7 >= 5, go right	7	succ stays 10	Continue search
14	root null, return succ 10	NULL	Return 10	Successor is 10

💡 Return successor node or NULL if none found

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 7	After Step 12	After Step 14
root	10	5	5	5	5	NULL
p	5	5	7	7	7	7
succ	NULL	NULL	NULL	NULL	10	10

Key Moments - 3 Insights

Why do we go to the leftmost node in the right subtree when the node has a right child?

Because the leftmost node in the right subtree is the smallest node greater than the target, making it the inorder successor (see execution_table step 5-6).

Why do we move up to ancestors when the node has no right child?

Because the successor is the nearest ancestor for which the node lies in its left subtree (see execution_table steps 11-14).

Why does the search for the node start at the root and move left or right?

Because BST property lets us decide direction: if target value is less than current node, go left; else go right (see execution_table steps 1-3).

Visual Quiz - 3 Questions

Look at the execution_table at step 5, which node does pointer p move to?

A Node 2

B Node 7

C Node 10

D Node 15

💡 Hint

Check the 'Pointer Changes' and 'Current Node' columns at step 5.

At which step does the algorithm decide to return node 10 as the successor?

A Step 14

B Step 12

C Step 7

D Step 3

💡 Hint

Look for the step where 'Return 10' is noted in 'Pointer Changes' and 'Visual State'.

If node 5 had no right child, how would the successor be found according to the execution flow?

A Go to leftmost node in right subtree

B Return NULL immediately

C Move up to ancestor where node is in left subtree

D Search entire tree again

💡 Hint

Refer to the concept_flow where no right child leads to ancestor search.

Concept Snapshot

BST Inorder Successor:
- If node has right child: successor = leftmost node in right subtree
- Else: successor = nearest ancestor where node is in left subtree
- Search node from root using BST property
- Return NULL if no successor found

Full Transcript

To find the inorder successor of a node in a BST, first locate the node starting from the root. If the node has a right child, the successor is the leftmost node in that right subtree. If no right child exists, move up the tree to find the nearest ancestor for which the node lies in the left subtree. If none found, successor is NULL. This process uses BST properties to decide direction at each step.

Practice

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

easy

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

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

C. The left child of the given node

D. The right child of the given node

Solution

1. Step 1: Understand inorder traversal in BST

   Inorder traversal visits nodes in ascending order of their keys.

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 B

4. Quick Check:

   Inorder successor = next bigger node [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 left child

2. Which of the following C function signatures correctly represents a function to find the inorder successor of a BST node?

easy

A. struct Node* inorderSuccessor(struct Node* root, struct Node* n);

B. int inorderSuccessor(int root, int n);

C. void inorderSuccessor(struct Node* root);

D. struct Node inorderSuccessor(struct Node n);

Solution

1. Step 1: Analyze function parameters

   The function needs the BST root and the node to find successor for, both as pointers.

2. Step 2: Analyze return type

   It should return a pointer to the successor node, so return type is struct Node*.

3. Final Answer:

   struct Node* inorderSuccessor(struct Node* root, struct Node* n); -> Option A

4. Quick Check:

   Correct signature uses pointers for nodes [OK]

Hint: Use pointers for nodes and return pointer to successor [OK]

Common Mistakes:

• Using int instead of struct Node*
• Missing node parameter
• Returning struct Node by value

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

        20
       /  \
     10    30
       \     \
       15    40

medium

A. 10

B. 30

C. 20

D. 40

Solution

1. Step 1: Locate node 15 and find its right subtree

   Node 15 has no right child, so successor is an ancestor.

2. Step 2: Move up to find the lowest ancestor greater than 15

   Parent 10 is less than 15, move up to 20 which is greater than 15.

3. Final Answer:

   20 -> Option C

4. Quick Check:

   Next bigger after 15 is 20 [OK]

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

Common Mistakes:

• Choosing right child 30 incorrectly
• Choosing smaller ancestor 10
• Confusing successor with predecessor

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

struct Node* inorderSuccessor(struct Node* root, struct Node* n) {
    if (n->right != NULL) {
        struct Node* temp = n->right;
        while (temp->left != NULL) {
            temp = temp->left;
        }
        return temp;
    }
    struct Node* succ = NULL;
    while (root != NULL) {
        if (n->data < root->data) {
            succ = root;
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return succ;
}

What is the main logical error in this code?

medium

A. It incorrectly updates successor when moving right

B. It returns the wrong node when node has right child

C. It uses a while loop instead of recursion

D. It does not handle the case when node has no right child

Solution

1. Step 1: Check handling of right child

   Code correctly finds leftmost node in right subtree if right child exists.

2. Step 2: Check updating successor when moving right

   In the else branch (n->data >= root->data), it incorrectly sets succ = root before moving right. Successor should NOT be updated when going right, as n is in (or at) the right subtree.

3. Step 3: Identify error

   The main logical error is incorrectly updating the successor when traversing right.

4. Final Answer:

   It incorrectly updates successor when moving right -> Option A

5. Quick Check:

   Successor updates only on left moves [OK]

Hint: Successor updates only when moving left in BST [OK]

Common Mistakes:

• Thinking recursion is required
• Updating successor when moving right
• Ignoring right subtree case

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

         20
        /  \
      10    30
     /  \  /  \
    5  15 25  40

If the node with value 25 has no right child, what is the inorder successor and why?

hard

A. 20, because it is the root

B. 40, because it is the right child of 30

C. No successor, because 25 has no right child

D. 30, because it is the lowest ancestor greater than 25

Solution

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

   Node 25 has no right child, so successor is an ancestor.

2. Step 2: Find lowest ancestor greater than 25

   Ancestor 30 is greater than 25 and is the lowest such ancestor.

3. Final Answer:

   30, because it is the lowest ancestor greater than 25 -> Option D

4. Quick Check:

   Successor = nearest bigger ancestor [OK]

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

Common Mistakes:

• Choosing right child 40 incorrectly
• Saying no successor exists
• Choosing root 20 incorrectly