BST Inorder Successor in DSA Python - Build from Scratch

BST Inorder Successor

📖 Scenario: You are working with a Binary Search Tree (BST) that stores numbers. You want to find the next bigger number after a given number in the tree. This is called the inorder successor.Think of the BST as a sorted list of numbers arranged in a tree shape. Finding the inorder successor means finding the number that comes right after a given number when you look at the numbers in order.

🎯 Goal: Build a program that creates a BST, then finds the inorder successor of a given node value.This will help you understand how to navigate trees and find specific nodes based on their order.

📋 What You'll Learn

Create a BST with specific nodes

Add a helper variable to store the target node value

Write a function to find the inorder successor of the target node

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

💡 Why This Matters

🌍 Real World

Finding the next bigger item in sorted data stored as a tree is useful in databases, file systems, and search engines.

💼 Career

Understanding BST traversal and successor logic is important for software engineers working with data structures, algorithms, and system design.

1

Create the BST nodes

Create a class called Node with an __init__ method that takes val, left, and right parameters. Then create the following BST structure by creating nodes and linking them:
root = Node(20), root.left = Node(10), root.right = Node(30), root.left.left = Node(5), root.left.right = Node(15), root.right.right = Node(40)

DSA Python

# Define Node class and create BST nodes as described
# Your code here

Hint

Define the Node class first. Then create the root node with value 20. Add left and right children as described.

2

Set the target node value

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

DSA Python

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

root = Node(20)
root.left = Node(10)
root.right = Node(30)
root.left.left = Node(5)
root.left.right = Node(15)
root.right.right = Node(40)

# Set the target node value
# Your code here

Hint

Just create a variable named target_val and assign 15 to it.

3

Write the inorder successor function

Write a function called inorder_successor that takes root and target_val as parameters. It should find the node with value target_val in the BST and return the node that is its inorder successor. Use the BST property and the following logic:
- If the node has a right child, the successor is the leftmost node in the right subtree.
- Otherwise, the successor is the lowest ancestor for which the node is in the left subtree.
Return None if no successor exists.

DSA Python

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

root = Node(20)
root.left = Node(10)
root.right = Node(30)
root.left.left = Node(5)
root.left.right = Node(15)
root.right.right = Node(40)

target_val = 15

# Write inorder_successor function below
# Your code here

Hint

Use a loop to find the target node. Keep track of a possible successor when moving left. If the node has a right child, go down to its leftmost child. Otherwise, return the stored successor.

4

Print the inorder successor value

Call the inorder_successor function with root and target_val. Then print the value of the returned node if it exists, or print None if there is no successor.

DSA Python

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

root = Node(20)
root.left = Node(10)
root.right = Node(30)
root.left.left = Node(5)
root.left.right = Node(15)
root.right.right = Node(40)

target_val = 15

def inorder_successor(root, target_val):
    # Find the target node
    current = root
    successor = None
    while current:
        if target_val  current.val:
            current = current.right
        else:
            break
    if current is None:
        return None
    # If right subtree exists, find leftmost node there
    if current.right:
        current = current.right
        while current.left:
            current = current.left
        return current
    # Otherwise, successor is ancestor stored earlier
    return successor

# Print the inorder successor value
# Your code here

Hint

Call the function and print the value of the returned node. If it is None, print None.

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