BST Inorder Predecessor in DSA Python - Deep Dive

Overview - BST Inorder Predecessor

What is it?

A Binary Search Tree (BST) is a tree where each node has at most two children, and the left child is smaller while the right child is larger than the node. The inorder predecessor of a node in a BST is the node that comes immediately before it when the tree is visited in sorted order (left-root-right). Finding the inorder predecessor helps us understand the relative position of nodes in the BST.

Why it matters

Knowing the inorder predecessor is important for tasks like deleting nodes from a BST or navigating the tree in sorted order. Without this concept, operations on BSTs would be inefficient or incorrect, making it hard to maintain sorted data or perform quick lookups. It helps keep data organized and accessible in many software systems.

Where it fits

Before learning this, you should understand what a BST is and how inorder traversal works. After this, you can learn about inorder successor, node deletion in BSTs, and balanced BSTs like AVL or Red-Black trees.

Mental Model

Core Idea

The inorder predecessor of a node in a BST is the largest node smaller than that node, found by looking left once and then as far right as possible.

Think of it like...

Imagine a line of people sorted by height. The inorder predecessor of a person is the tallest person who is just a bit shorter standing immediately to their left.

       20
      /  \
    10    30
      \     \
      15    40

Inorder traversal: 10 -> 15 -> 20 -> 30 -> 40
For node 20, inorder predecessor is 15 (largest smaller number).
For node 15, inorder predecessor is 10.
For node 10, no predecessor (null).

Build-Up - 7 Steps

1

Foundation

Understanding BST Structure

Concept: Learn what a BST is and how nodes are arranged.

A BST is a tree where each node has a value. Left child nodes have smaller values, right child nodes have larger values. This keeps the tree sorted. For example, if root is 20, left child can be 10, right child 30.

Result

You can tell if a tree is a BST by checking if left < node < right for every node.

Understanding BST structure is essential because the inorder predecessor depends on this sorted arrangement.

2

Foundation

Inorder Traversal Basics

Concept: Learn how inorder traversal visits nodes in sorted order.

Inorder traversal visits left subtree, then node, then right subtree. For BST, this means visiting nodes from smallest to largest. For example, for tree with nodes 10, 15, 20, 30, 40, inorder traversal visits them in that order.

Result

Inorder traversal outputs nodes sorted: 10 -> 15 -> 20 -> 30 -> 40

Knowing inorder traversal order helps us understand what 'predecessor' means in the BST context.

3

Intermediate

Defining Inorder Predecessor

🤔Before reading on: do you think the inorder predecessor is always the left child? Commit to your answer.

Concept: The inorder predecessor is the node visited just before the current node in inorder traversal, not always the left child.

If a node has a left child, the predecessor is the rightmost node in that left subtree. If no left child, predecessor is one of the ancestors where the node lies in the right subtree.

Result

For node 20, predecessor is 15 (rightmost in left subtree). For node 15, predecessor is 10 (left child with no right child). For node 10, no predecessor.

Understanding that predecessor depends on subtree structure and ancestors prevents wrong assumptions about simple left-child relationships.

4

Intermediate

Finding Predecessor When Left Subtree Exists

🤔Before reading on: if a node has a left child, do you think the predecessor is the left child itself or somewhere deeper? Commit to your answer.

Concept: When left subtree exists, predecessor is the rightmost node in that subtree.

Start at left child, then keep moving right until no more right child. That node is the predecessor. For example, node 20's left child is 10, which has right child 15. 15 has no right child, so 15 is predecessor.

Result

Predecessor found by going left once, then right as far as possible.

Knowing to go right inside left subtree ensures finding the largest smaller value, not just any smaller value.

5

Intermediate

Finding Predecessor Without Left Subtree

🤔Before reading on: if a node has no left child, do you think the predecessor is below or above it in the tree? Commit to your answer.

Concept: If no left subtree, predecessor is an ancestor node where current node lies in its right subtree.

Move up the tree until you find a node that is right child of its parent. That parent is the predecessor. For example, if node 15 has no left child, its predecessor is 10 if 15 is right child of 10.

Result

Predecessor found by moving up ancestors until a right turn is found.

Understanding ancestor traversal prevents missing predecessors when left subtree is absent.

6

Advanced

Implementing Predecessor in Python

🤔Before reading on: do you think the code should handle both left subtree and ancestor cases separately? Commit to your answer.

Concept: Code must check if left child exists to find predecessor; else traverse ancestors.

def inorder_predecessor(root, node): # Case 1: Left subtree exists if node.left: pred = node.left while pred.right: pred = pred.right return pred # Case 2: No left subtree pred = None current = root while current: if node.val > current.val: pred = current current = current.right elif node.val < current.val: current = current.left else: break return pred # Example usage: # Tree: 20 # / \ # 10 30 # \ \ # 15 40 # Find predecessor of 20 -> 15

Result

Function returns correct predecessor node or None if none exists.

Knowing to separate cases in code matches the mental model and ensures correctness.

7

Expert

Predecessor in Node Deletion and Balancing

🤔Before reading on: do you think predecessor is only useful for traversal? Commit to your answer.

Concept: In deletion of nodes with two children, predecessor replaces the deleted node to maintain BST properties. Also used in balancing trees.

When deleting a node with two children, replace it with its inorder predecessor (or successor). This keeps the tree sorted. Balancing algorithms may use predecessor info to rotate nodes correctly.

Result

Predecessor helps maintain BST integrity during complex operations.

Understanding predecessor's role in deletion and balancing reveals its practical importance beyond traversal.

Under the Hood

The BST property ensures left subtree nodes are smaller and right subtree nodes are larger. The inorder predecessor is found by exploiting this property: if left subtree exists, the rightmost node there is the largest smaller node. If not, ancestors are checked by moving up until a node is found where the current node lies in its right subtree. This relies on parent-child relationships and BST ordering.

Why designed this way?

BSTs were designed to allow fast search, insert, and delete operations by maintaining order. The inorder predecessor concept fits naturally because inorder traversal lists nodes in sorted order. Using predecessor in deletion avoids breaking BST properties. Alternatives like unordered trees lack this efficient navigation.

          [Root]
            20
           /  \
      [L]10    30[R]
         \       \
         15      40

Finding predecessor of 20:
  - Go left to 10
  - Go right as far as possible: 15

If no left subtree:
  - Move up ancestors until current node is right child
  - That ancestor is predecessor

Traversal path:
  node -> left child -> rightmost descendant
  or
  node -> ancestors moving up

Myth Busters - 4 Common Misconceptions

Quick: Is the inorder predecessor always the left child? Commit yes or no.

Common Belief: The inorder predecessor is always the left child of the node.

Reality: The predecessor is the rightmost node in the left subtree, not necessarily the immediate left child.

Why it matters: Assuming left child is predecessor leads to wrong results and bugs in tree operations.

Quick: If a node has no left child, does it have no predecessor? Commit yes or no.

Common Belief: If a node has no left child, it has no inorder predecessor.

Reality: If no left child, predecessor is found by moving up ancestors until a node is found where current node is in right subtree.

Why it matters: Ignoring ancestor traversal misses valid predecessors, causing errors in deletion or traversal.

Quick: Is inorder predecessor always smaller than the node? Commit yes or no.

Common Belief: Inorder predecessor can sometimes be larger or equal to the node.

Reality: By definition, inorder predecessor is always smaller than the node in BST.

Why it matters: Misunderstanding this breaks BST properties and leads to incorrect tree structure.

Quick: Can the inorder predecessor be the node itself? Commit yes or no.

Common Belief: Sometimes the node is its own predecessor.

Reality: A node cannot be its own predecessor; predecessor is always a different node or null.

Why it matters: Confusing this causes infinite loops or incorrect traversal results.

Expert Zone

1

In threaded BSTs, inorder predecessor pointers are stored explicitly to speed up traversal without recursion or stacks.

2

When deleting nodes, choosing predecessor vs successor as replacement affects tree balance subtly and can impact performance.

3

In augmented BSTs (like order statistic trees), predecessor queries combine with rank information for advanced queries.

When NOT to use

In non-BST trees like heaps or general binary trees, inorder predecessor concept does not apply. Use other traversal or search methods instead.

Production Patterns

In databases and file systems using BST-like indexes, predecessor queries help implement range queries and rollback operations efficiently.

Connections

Inorder Successor

Opposite concept; successor is next node in sorted order after current node.

Understanding predecessor clarifies successor logic since both rely on BST structure and traversal order.

Doubly Linked List

Both have predecessor and successor relationships linking elements in order.

Knowing BST predecessor helps understand how doubly linked lists maintain bidirectional order.

Version Control Systems (Git)

Predecessor concept relates to finding previous commits in history graph.

Understanding predecessor in BST helps grasp how Git finds previous states, showing cross-domain pattern of 'previous element' navigation.

Common Pitfalls

#1 Assuming left child is always predecessor.

Wrong approach:

def predecessor(node):
return node.left # Wrong: ignores right subtree of left child

Correct approach:

def predecessor(node):
if node.left:
pred = node.left
while pred.right:
pred = pred.right
return pred
return None

Root cause:

Misunderstanding that predecessor is largest node smaller than current, not just immediate left child.

#2 Not handling case when no left subtree exists.

Wrong approach:

def predecessor(node):
if node.left:
# find rightmost in left subtree
...
else:
return None # Wrong: misses ancestor traversal

Correct approach:

def predecessor(root, node):
if node.left:
# find rightmost in left subtree
...
else:
pred = None
current = root
while current:
if node.val > current.val:
pred = current
current = current.right
elif node.val < current.val:
current = current.left
else:
break
return pred

Root cause:

Ignoring ancestor traversal when left subtree is absent.

#3 Returning node itself as predecessor.

Wrong approach:

def predecessor(node):
return node # Wrong: node cannot be its own predecessor

Correct approach:

def predecessor(node):
# Implement proper logic to find different node or None
...

Root cause:

Confusing current node with its predecessor.

Key Takeaways

The inorder predecessor of a BST node is the largest node smaller than it, found by going left once and then right as far as possible, or by moving up ancestors if no left subtree exists.

Understanding predecessor is crucial for correct BST operations like deletion and inorder traversal.

Predecessor is not always the immediate left child; it may be deeper in the left subtree or an ancestor.

Properly handling both left subtree and ancestor cases in code ensures accurate and efficient BST navigation.

Misconceptions about predecessor lead to bugs and incorrect tree behavior, so clear mental models and careful implementation are essential.

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