BST Inorder Predecessor in DSA Python - Execution Trace

Concept Flow - BST Inorder Predecessor

Start at root node

↓

Search for target node

↓

Found target node?

No→Return None

Yes↓

Does target have left child?

Yes→Go to left child

↓

Go right as far as possible

↓

Go up to ancestor where target is in right subtree

↓

Return that ancestor as predecessor

↓

Done

Find the node's inorder predecessor by searching the tree, then either going left and rightmost, or up to ancestor.

Execution Sample

DSA Python

def inorder_predecessor(root, target):
    # Find target node
    # If left child exists, go left then rightmost
    # Else go up to ancestor where target is in right subtree
    pass

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

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start at root	20	None	20 / \ 10 30
2	Search for target 10	20 -> 10	Move left	20 / \ 10 30
3	Found target 10	10	None	20 / \ 10 30
4	Check left child of 10	10	None	20 / \ 10 30
5	Left child is 5, go left	5	Move left	20 / \ 10 30 / 5
6	Go rightmost from 5	5	None	20 / \ 10 30 / 5
7	No right child of 5	5	None	20 / \ 10 30 / 5
8	Predecessor is 5	5	None	20 / \ 10 30 / 5
9	Return predecessor 5	5	None	20 / \ 10 30 / 5

💡 Predecessor found as rightmost node in left subtree of target.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 7	Final
current_node	20	10	5	5	5
predecessor	None	None	None	5	5

Key Moments - 3 Insights

Why do we go to the rightmost node in the left subtree?

Because the inorder predecessor is the largest node smaller than the target, which is the rightmost node in the left subtree (see steps 5-7 in execution_table).

What if the target node has no left child?

Then we move up to the ancestor where the target node is in the right subtree (not shown in this example), because the predecessor is an ancestor smaller than the target.

Why do we stop searching when we find the target node?

Because we need to find the predecessor of that specific node, so once found (step 3), we proceed to find its predecessor.

Visual Quiz - 3 Questions

Look at the execution_table, what is the current_node at Step 5?

A 5

B 20

C 10

D 30

💡 Hint

Check the 'Current Node' column at Step 5 in execution_table.

At which step does the algorithm confirm the predecessor node?

A Step 4

B Step 6

C Step 8

D Step 9

💡 Hint

Look for the step where 'Predecessor is 5' is noted in the Operation column.

If the target node had no left child, what would the algorithm do next?

A Return None immediately

B Go up to ancestor where target is in right subtree

C Go to the right child of target

D Go left again

💡 Hint

Refer to the concept_flow where no left child leads to moving up to ancestor.

Concept Snapshot

BST Inorder Predecessor:
- Find target node in BST
- If target has left child: go left once, then rightmost
- Else: move up to ancestor where target is in right subtree
- Predecessor is largest smaller node than target
- Returns None if no predecessor exists

Full Transcript

To find the inorder predecessor in a BST, start at the root and search for the target node. Once found, if the target has a left child, go to that left child and then keep going right until no more right child exists. That node is the predecessor. If the target has no left child, move up the tree to find an ancestor where the target is in the right subtree; that ancestor is the predecessor. If no such ancestor exists, the predecessor is None. This process ensures finding the largest node smaller than the target in the BST.

Practice

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

easy

A. The node with the largest value smaller than the given node

B. The node with the smallest value larger than the given node

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 for BST, so predecessor is the previous node in this order.

2. Step 2: Define inorder predecessor

   The inorder predecessor is the node with the largest value smaller than the current node's value.

3. Final Answer:

   The node with the largest value smaller than the given node -> Option A

4. Quick Check:

   Inorder predecessor = largest smaller value [OK]

Hint: Predecessor is just before current node in sorted order [OK]

Common Mistakes:

• Confusing predecessor with successor
• Thinking predecessor is always left child
• Assuming predecessor is the parent node

2. Which of the following Python code snippets correctly finds the inorder predecessor of a node with a left subtree in a BST?

easy

A. temp = node.right
while temp.right:
temp = temp.right
return temp

B. temp = node.right
while temp.left:
temp = temp.left
return temp

C. temp = node.left
while temp.left:
temp = temp.left
return temp

D. temp = node.left
while temp.right:
temp = temp.right
return temp

Solution

1. Step 1: Identify inorder predecessor logic for left subtree

   If node has left child, predecessor is the rightmost node in left subtree.

2. Step 2: Check code correctness

   Code D moves to left child, then goes right as far as possible, correctly finding predecessor.

3. Final Answer:

   Code snippet D correctly finds the inorder predecessor -> Option D

4. Quick Check:

   Left subtree's rightmost node = predecessor [OK]

Hint: Go left once, then right as far as possible [OK]

Common Mistakes:

• Going right subtree instead of left
• Going left repeatedly instead of right in left subtree
• Returning left child directly without traversal

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

       20
      /  \
    10    30
      \     \
      15    40

medium

A. 20

B. 15

C. 10

D. None

Solution

1. Step 1: Locate node 15 and check left subtree

   Node 15 has no left child, so predecessor is ancestor smaller than 15.

2. Step 2: Find nearest ancestor smaller than 15

   Ancestor 10 is smaller than 15 and is the closest on path to root.

3. Final Answer:

   10 -> Option C

4. Quick Check:

   Predecessor of 15 is 10 [OK]

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

Common Mistakes:

• Choosing 20 which is larger
• Choosing node itself as predecessor
• Assuming predecessor is None without checking ancestors

4. The following code attempts to find the inorder predecessor of a node in a BST but has a bug. What is the bug?

def inorder_predecessor(root, node):
    if node.left:
        temp = node.left
        while temp.left:
            temp = temp.left
        return temp
    else:
        predecessor = None
        while root:
            if node.val > root.val:
                predecessor = root
                root = root.right
            else:
                root = root.left
        return predecessor

medium

A. The else block incorrectly updates predecessor

B. The while loop should check temp.right, not temp.left

C. The function does not handle empty tree

D. The function should return None if node has no left child

Solution

1. Step 1: Analyze left subtree traversal

   In left subtree, predecessor is rightmost node, so loop should go right, not left.

2. Step 2: Identify correct traversal direction

   Changing while temp.left to while temp.right fixes the bug.

3. Final Answer:

   The while loop should check temp.right, not temp.left -> Option B

4. Quick Check:

   Predecessor in left subtree = rightmost node [OK]

Hint: Go right in left subtree, not left [OK]

Common Mistakes:

• Looping left instead of right in left subtree
• Ignoring else block logic
• Not returning predecessor correctly

5. You want to find the inorder predecessor of a node in a BST that does NOT have a left child. Which approach correctly finds the predecessor?

hard

A. Traverse from root, track the last node smaller than current node

B. Return the rightmost node in the left subtree

C. Return the parent node if it is smaller than the current node

D. Return the left child of the current node

Solution

1. Step 1: Understand no left child case

   If node has no left child, predecessor is an ancestor smaller than node.

2. Step 2: Use root traversal to track predecessor

   Traverse from root, update predecessor when node value is greater than root's value.

3. Step 3: Return last tracked smaller ancestor

   This gives the inorder predecessor correctly.

4. Final Answer:

   Traverse from root, track the last node smaller than current node -> Option A

5. Quick Check:

   No left child -> track smaller ancestor [OK]

Hint: Track last smaller ancestor from root [OK]

Common Mistakes:

• Returning parent without checking value
• Returning left child when none exists
• Trying to find predecessor in left subtree when none exists