BST Inorder Successor in DSA Python - Execution Trace

Concept Flow - BST Inorder Successor

Start at root

↓

Find target node

↓

Does target have right child?

Yes→Go to right child

↓

Find leftmost node

↓

Go up to ancestor

↓

Return successor or None

Find the node, then if it has right child, successor is leftmost node in right subtree; else go up ancestors to find first bigger node.

Execution Sample

DSA Python

def inorder_successor(root, target):
    # Find target node
    # If right child exists, go leftmost in right subtree
    # Else go up ancestors to find successor
    pass

This code finds the inorder successor of a target node in a BST.

Execution Table

Step	Operation	Nodes in Tree (value)	Pointer Changes	Visual State
1	Start at root (20), search for target 15	[20, 10, 30, 5, 15, 25, 35]	current = 20	20 / \ 10 30 / \ / \ 5 15 25 35
2	Move left to 10 (since 15 < 20)	[20, 10, 30, 5, 15, 25, 35]	current = 10	20 / \ 10 30 / \ / \ 5 15 25 35
3	Move right to 15 (since 15 > 10)	[20, 10, 30, 5, 15, 25, 35]	current = 15	20 / \ 10 30 / \ / \ 5 15 25 35
4	Check if 15 has right child	[20, 10, 30, 5, 15, 25, 35]	15.right = None	No right child
5	Go up ancestors to find first ancestor > 15	[20, 10, 30, 5, 15, 25, 35]	successor = 20 (since 20 > 15)	Successor found: 20
6	Return successor 20	[20, 10, 30, 5, 15, 25, 35]	Return 20	Successor: 20

💡 Found successor 20 after checking right child absence and moving up ancestors

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
current	root (20)	20	10	15	15	15	15
successor	None	None	None	None	None	20	20

Key Moments - 3 Insights

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

Because if the target has a right child, the inorder successor is the leftmost node in that right subtree, as shown in execution_table step 4.

Why do we move up ancestors if the target node has no right child?

Because the successor is the first ancestor node with a value greater than the target, as shown in execution_table step 5.

What if the target node is the largest node in the BST?

Then it has no inorder successor, because no ancestor or right subtree node is greater, so the function returns None (not shown in this example).

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the current node's value?

A 10

B 20

C 15

D 30

💡 Hint

Check the 'Pointer Changes' column at step 3 in execution_table.

At which step do we find that the target node has no right child?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look for the step mentioning 'Check if 15 has right child' in execution_table.

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

A Step 5 would be skipped

B Step 4 would show moving to right child and then leftmost node

C Step 6 would return None

D Step 1 would change to start at right child

💡 Hint

Refer to the concept_flow and execution_table step 4 for right child presence.

Concept Snapshot

BST Inorder Successor:
- Find target node in BST
- If target has right child: successor = leftmost node in right subtree
- Else: successor = first ancestor with value > target
- If no such ancestor, successor is None
- Used in BST traversal and deletion

Full Transcript

To find the inorder successor of a node in a BST, first locate the target node by comparing values from the root. If the target node has a right child, the successor is the leftmost node in that right subtree. If no right child exists, move up the ancestors to find the first node with a value greater than the target. If none is found, the target has no successor. This process is shown step-by-step in the execution table, tracking the current node and successor pointers, and the tree's visual state.

Practice

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

easy

A. The left child of the given node

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

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

D. The root node of the BST

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 the given node.

3. Final Answer:

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

4. Quick Check:

   Inorder successor = next larger 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 parent node

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

easy

A. def inorder_successor(self, p: 'Node') -> 'Node':

B. def inorder_successor(self, root: 'Node', p: 'Node') -> 'Node':

C. def inorder_successor(root, p):

D. def inorder_successor(p: 'Node') -> 'Node':

Solution

1. Step 1: Identify parameters needed

   To find inorder successor, we need the BST root and the target node p.

2. Step 2: Check function signature correctness

   def inorder_successor(self, root: 'Node', p: 'Node') -> 'Node': includes self (method), root, and p with type hints, matching common BST method style.

3. Final Answer:

   def inorder_successor(self, root: 'Node', p: 'Node') -> 'Node': -> Option B

4. Quick Check:

   Correct parameters and type hints [OK]

Hint: Include root and target node as parameters with type hints [OK]

Common Mistakes:

• Missing root parameter
• Omitting type hints in modern Python
• Wrong parameter order or missing self

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. 40

C. 30

D. 20

Solution

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

   Node 15 has no right child, so successor is one of its ancestors.

2. Step 2: Find the lowest ancestor whose left child is also ancestor of 15

   Node 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 D

4. Quick Check:

   Next bigger after 15 is 20 [OK]

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

Common Mistakes:

• Choosing right child when none exists
• Picking 30 or 40 which are too large
• Confusing predecessor with successor

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

def inorder_successor(root, p):
    if p.right:
        curr = p.right
        while curr.left:
            curr = curr.left
        return curr
    else:
        curr = root
        successor = None
        while curr:
            if p.val < curr.val:
                successor = curr
                curr = curr.left
            else:
                curr = curr.right
        return None

medium

A. The function returns None instead of successor at the end

B. The while loop condition is incorrect

C. The function does not check if p has a right child

D. The variable successor is never updated

Solution

1. Step 1: Analyze return statements

   When p has no right child, function finds successor but returns None instead of successor.

2. Step 2: Identify missing return of successor

   At the end of else block, it should return successor, not None.

3. Final Answer:

   The function returns None instead of successor at the end -> Option A

4. Quick Check:

   Return successor, not None [OK]

Hint: Return successor variable after loop, not None [OK]

Common Mistakes:

• Returning None instead of found successor
• Not updating successor inside loop
• Ignoring right subtree case

5. You have a BST where each node has a parent pointer. How can you find the inorder successor of a node efficiently using the parent pointer?

hard

A. If node has right child, successor is leftmost node in right subtree; else go up until node is left child of its parent

B. If node has left child, successor is rightmost node in left subtree; else go up until node is right child of its parent

C. Successor is always the parent node

D. Successor is the left child of the node's parent

Solution

1. Step 1: Check if node has right child

   If yes, successor is the leftmost node in right subtree.

2. Step 2: If no right child, move up using parent pointer

   Go up until current node is left child of its parent; that parent is successor.

3. Final Answer:

   If node has right child, successor is leftmost node in right subtree; else go up until node is left child of its parent -> Option A

4. Quick Check:

   Use right subtree or climb parents [OK]

Hint: Use right subtree or climb parents until left child [OK]

Common Mistakes:

• Confusing left and right child cases
• Assuming successor is always parent
• Not using parent pointer to climb up