BST Inorder Successor in DSA C++ - Execution Trace

Concept Flow - BST Inorder Successor

Start at root

↓

Find node with given key

↓

Does node have right child?

Yes→Go to right child

↓

Find leftmost node in right subtree

↓

Go up to parent while node is right child

↓

Return parent as successor or NULL if none

Find the node, then if it has right child, successor is leftmost in right subtree; else go up to find first 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 by checking right subtree or climbing up ancestors.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start at root to find node 5	10	root=10	10 / \ 5 15
2	Go left since 5 < 10	5	root=5	10 / \ 5 15
3	Node 5 found, check right child	5	p=5	10 / \ 5 15
4	Node 5 has right child 7, go right	7	p=7	10 / \ 5 15 \ 7
5	Find leftmost in right subtree	7	p=7	10 / \ 5 15 \ 7
6	7 has no left child, successor is 7	7	return 7	10 / \ 5 15 \ 7
7	Return successor 7	7	return	Successor: 7
8	Alternate case: Node 15 with no right child	15	p=15	10 / \ 5 15
9	Go up to parent while node is right child	15	root=10	10 / \ 5 15
10	15 is right child of 10, move up	10	root=NULL	10 / \ 5 15
11	No ancestor where node is left child, successor NULL	NULL	return NULL	Successor: NULL

💡 Traversal ends when successor found or no ancestor left where node is left child.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 9	After Step 11
root	10	5	7	7	10	NULL
p	5	5	7	7	15	15
succ	NULL	NULL	NULL	7	NULL	NULL

Key Moments - 3 Insights

Why do we check the right child of the node first?

Because if the node has a right child, the inorder successor is the leftmost node in that right subtree, as shown in steps 3-6 of the execution_table.

What if the node has no right child? How do we find the successor?

We move up the tree to find the first ancestor where the node is in the left subtree, as shown in steps 8-11 where we climb from node 15 up to root 10 and find no successor.

Why do we stop when root becomes NULL in the upward traversal?

Because it means we reached the top of the tree without finding an ancestor where the node is a left child, so the node has no inorder successor (step 11).

Visual Quiz - 3 Questions

Look at the execution_table, what is the successor of node 5 at step 6?

A Node 7

B Node 10

C Node 15

D NULL

💡 Hint

Check the Visual State and Operation columns at step 6 where successor is returned as 7.

At which step does the traversal end with no successor found for node 15?

A Step 7

B Step 9

C Step 11

D Step 4

💡 Hint

Look at the exit_note and rows 10-11 where root becomes NULL and successor is NULL.

If node 5 had no right child, which operation would the algorithm perform next?

A Return node 7 as successor

B Go up to parent to find ancestor where node is left child

C Return NULL immediately

D Go to left child

💡 Hint

Refer to key_moments and execution_table steps 8-11 for the case when right child is absent.

Concept Snapshot

BST Inorder Successor:
- If node has right child, successor = leftmost node in right subtree
- Else, climb ancestors to find first node where current node is in left subtree
- Return NULL if no such ancestor
- Used in BST traversal and deletion
- Time: O(h) where h = tree height

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, move up the tree to find the first ancestor where the node is in the left subtree. If none found, successor is NULL. This process is shown step-by-step in the execution table with pointer changes and visual tree states. Key moments clarify why we check right child first and how upward traversal works. 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 left child of the given node

D. The right 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 with a key greater than the current node.

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++ function signatures correctly represents a function to find the inorder successor of a BST node given the root and the node? Assume Node is a struct with int key, and left/right pointers.

easy

A. Node inorderSuccessor(Node root, Node p);

B. int inorderSuccessor(Node root, int p);

C. void inorderSuccessor(Node* root, Node* p);

D. Node* inorderSuccessor(Node* root, Node* p);

Solution

1. Step 1: Analyze parameter types

   The function needs access to the BST root and the target node pointer, so pointers are required.

2. Step 2: Analyze return type

   The function should return a pointer to the successor node or nullptr if none exists.

3. Final Answer:

   Node* inorderSuccessor(Node* root, Node* p); -> Option D

4. Quick Check:

   Use pointers for tree nodes and return pointer [OK]

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

Common Mistakes:

• Passing nodes by value instead of pointer
• Returning void instead of Node*
• Using int instead of Node* for node parameters

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

        20
       /  \
     10    30
       \     \
       15    40

medium

A. 10

B. 20

C. 30

D. 40

Solution

1. Step 1: Locate node 15 and find successor

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

2. Step 2: Identify successor in BST

   20 is the parent of 15's ancestor and 15 is in left subtree of 20, so successor is 20.

3. Final Answer:

   20 -> Option B

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 40 which is too far
• Choosing 10 which is smaller

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

Node* inorderSuccessor(Node* root, Node* p) {
    if (p->right != nullptr) {
        Node* curr = p->right;
        while (curr->left != nullptr) {
            curr = curr->left;
        }
        return curr;
    }
    Node* succ = nullptr;
    while (root != nullptr) {
        if (p->key < root->key) {
            succ = root;
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return succ;
}

What is the bug in this code?

medium

A. It does not check if p has a left child

B. It incorrectly updates succ when p->key == root->key

C. It does not handle the case when p is nullptr

D. It returns the wrong node when p has a right child

Solution

1. Step 1: Check null pointer dereference

   The code immediately accesses p->right and later p->key without verifying if p is nullptr, leading to a segmentation fault.

2. Step 2: Verify other logic

   Right subtree min is correctly found. Ancestor search properly sets succ only on left branches and handles equality by traversing right (null since no right child).

3. Final Answer:

   It does not handle the case when p is nullptr -> Option C

4. Quick Check:

   Missing p == nullptr check before dereference [OK]

Hint: Missing nullptr check for input node p [OK]

Common Mistakes:

• Ignoring nullptr checks for p
• Confusing left child check for successor
• Assuming bug in right subtree handling

5. You have a BST with nodes having keys: 5, 3, 7, 2, 4, 6, 8. You want to find the inorder successor of node with key 7. Which of the following is the correct approach to find it efficiently?

hard

A. If node 7 has right child, successor is leftmost node in right subtree; else, go up to first ancestor larger than 7

B. Successor is always the right child of node 7

C. Successor is the parent of node 7 regardless of children

D. Successor is the left child of node 7

Solution

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

   Node 7 has right child 8, so successor is leftmost node in right subtree, which is 8 itself.

2. Step 2: If no right child, find first ancestor larger than node

   This step is for cases where right child is absent, not applicable here.

3. Final Answer:

   If node 7 has right child, successor is leftmost node in right subtree; else, go up to first ancestor larger than 7 -> Option A

4. Quick Check:

   Right child exists, successor = leftmost right subtree [OK]

Hint: Check right subtree first; else climb ancestors [OK]

Common Mistakes:

• Assuming successor is always right child
• Ignoring ancestor climbing when no right child
• Confusing successor with parent node