BST Inorder Predecessor in DSA Python

Mental Model

The inorder predecessor of a node in a BST is the node that comes just before it when we list all nodes in sorted order.

Analogy: Imagine a line of people sorted by height. The inorder predecessor of a person is the person just shorter standing immediately before them.

      5
     / \
    3   7
   / \   \
  2   4   8
↑(curr=4)

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, find inorder predecessor of node with value 4

Goal: Find the node that comes just before 4 in the sorted order of BST nodes

Step 1: Start at node 4, check if it has left child

5 -> 3 -> 7 -> 2 -> [4] -> 8

Why: If node has left subtree, predecessor is max in that subtree

Step 2: Node 4 has no left child, so move up to parent nodes to find predecessor

5 -> 3 -> 7 -> 2 -> [4] -> 8

Why: Without left subtree, predecessor is nearest ancestor smaller than node

Step 3: Move up to parent 3, since 4 > 3, predecessor is 3

5 -> [3] -> 7 -> 2 -> 4 -> 8

Why: 3 is the last node smaller than 4 on path to root

Result:

3

Annotated Code

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None

def insert(root, val):
    if root is None:
        return Node(val)
    if val < root.val:
        left_child = insert(root.left, val)
        root.left = left_child
        left_child.parent = root
    else:
        right_child = insert(root.right, val)
        root.right = right_child
        right_child.parent = root
    return root

def find_node(root, val):
    if root is None or root.val == val:
        return root
    if val < root.val:
        return find_node(root.left, val)
    else:
        return find_node(root.right, val)

def max_node(node):
    while node.right:
        node = node.right
    return node

def inorder_predecessor(node):
    # If left subtree exists, predecessor is max in left subtree
    if node.left:
        return max_node(node.left)
    # Otherwise, go up until we find a node that is right child of its parent
    curr = node
    while curr.parent and curr == curr.parent.left:
        curr = curr.parent
    return curr.parent

# Build BST
root = None
for v in [5,3,7,2,4,8]:
    root = insert(root, v)

# Find node 4
target = find_node(root, 4)

# Find predecessor
pred = inorder_predecessor(target)
if pred:
    print(pred.val)
else:
    print('No predecessor')

if node.left:

Check if node has left subtree to find predecessor there

return max_node(node.left)

Predecessor is max node in left subtree

while curr.parent and curr == curr.parent.left:

Move up until node is right child of its parent

return curr.parent

Return parent as predecessor or None if no predecessor

Output

3

Complexity Analysis

Time: O(h) because we traverse up or down the tree height h to find predecessor

Space: O(1) because we use only a few pointers without extra data structures

vs Alternative: Naive approach would do inorder traversal of whole tree O(n), this method is faster by using BST properties

Edge Cases

Node has no left subtree and is the smallest node

No predecessor exists, function returns None

DSA Python

return curr.parent

Node has left subtree

Predecessor is max node in left subtree

DSA Python

if node.left:
    return max_node(node.left)

Node is root with no left subtree

No predecessor, returns None

DSA Python

while curr.parent and curr == curr.parent.left:
    curr = curr.parent

When to Use This Pattern

When asked for the previous node in sorted order in a BST, use the inorder predecessor pattern to find it efficiently using tree structure.

Common Mistakes

Mistake: Trying to find predecessor by full inorder traversal instead of using BST properties
Fix: Use left subtree max or move up to parent until node is right child

Mistake: Not handling case when node has no left subtree and is smallest
Fix: Return None when no valid predecessor found after moving up

Summary

Finds the node that comes just before a given node in BST sorted order.

Use when you need the previous smaller value node in BST without full traversal.

If left subtree exists, predecessor is max there; else move up to find ancestor smaller than node.

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