BST Inorder Predecessor in DSA Python - Build from Scratch

BST Inorder Predecessor

📖 Scenario: You are working with a Binary Search Tree (BST) that stores numbers. You want to find the inorder predecessor of a given node. The inorder predecessor is the node with the largest value smaller than the given node's value.This is useful in many real-world cases like finding the previous event in a timeline or the closest smaller price in a sorted list of prices.

🎯 Goal: Build a program that creates a BST, sets a target node value, finds the inorder predecessor of that node, and prints the predecessor's value.

📋 What You'll Learn

Create a BST by inserting nodes with given values

Set a target node value to find its inorder predecessor

Implement a function to find the inorder predecessor in the BST

Print the value of the inorder predecessor or None if it does not exist

💡 Why This Matters

🌍 Real World

Finding the inorder predecessor helps in database indexing, event timeline navigation, and version control systems where you need the closest smaller value before a given key.

💼 Career

Understanding BST operations like inorder predecessor is important for software engineers working on search algorithms, database engines, and coding interviews.

1

Create the BST Node class and insert nodes

Create a class called Node with an __init__ method that takes val and sets self.val, self.left, and self.right to None. Then create a function called insert that takes root and val and inserts a new node with val into the BST. Finally, create a BST by inserting these values in order: 20, 10, 30, 5, 15, 25, 35. Store the root in a variable called root.

DSA Python

# Your code here

Hint

Define the Node class first. Then write the insert function that adds nodes to the BST. Use a loop to insert all values into the BST.

2

Set the target node value

Create a variable called target_val and set it to 25. This is the value of the node whose inorder predecessor you want to find.

DSA Python

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

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

root = None
for v in [20, 10, 30, 5, 15, 25, 35]:
    root = insert(root, v)

# Set the target node value
# Your code here

Hint

Just create a variable named target_val and assign it the value 25.

3

Implement the function to find the inorder predecessor

Write a function called find_inorder_predecessor that takes root and target_val. It should find the node with target_val in the BST and return the value of its inorder predecessor. If the node has a left subtree, the predecessor is the rightmost node in that subtree. Otherwise, the predecessor is the last node for which the target node is in the right subtree. Return None if no predecessor exists.

DSA Python

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

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

root = None
for v in [20, 10, 30, 5, 15, 25, 35]:
    root = insert(root, v)

target_val = 25

# Write the find_inorder_predecessor function below
# Your code here

Hint

Use a loop to find the predecessor by comparing values. Then find the target node. If it has a left child, find the rightmost node in that left subtree. Otherwise, return the last smaller node found.

4

Print the inorder predecessor value

Use print to display the result of calling find_inorder_predecessor(root, target_val). This will show the inorder predecessor value or None if it does not exist.

DSA Python

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

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

def find_inorder_predecessor(root, target_val):
    predecessor = None
    current = root
    while current:
        if target_val <= current.val:
            current = current.left
        else:
            predecessor = current
            current = current.right
    # Now predecessor is the last node smaller than target_val
    # Check if target node has left subtree
    def find_node(root, val):
        if root is None:
            return None
        if val == root.val:
            return root
        elif val < root.val:
            return find_node(root.left, val)
        else:
            return find_node(root.right, val)

    target_node = find_node(root, target_val)
    if target_node and target_node.left:
        temp = target_node.left
        while temp.right:
            temp = temp.right
        return temp.val
    if predecessor:
        return predecessor.val
    return None

root = None
for v in [20, 10, 30, 5, 15, 25, 35]:
    root = insert(root, v)

target_val = 25

# Print the inorder predecessor value
# Your code here

Hint

Call the function with root and target_val and print the result.

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