BST Inorder Successor in DSA Python

Mental Model

The inorder successor of a node in a BST is the next node in sorted order. We find it by looking right once, then left as far as possible, or by moving up until we find a bigger ancestor.

Analogy: Imagine a line of people sorted by height. To find who stands just after you, you look to the right and then as far left as possible, or if none, you look back up the line to find the next taller person.

      20
     /  \
   10    30
     \     \
     15    40

Node: 15 ↑

Dry Run Walkthrough

Input: BST: 20 -> 10 -> 30 -> 15 -> 40, find inorder successor of 15

Goal: Find the node that comes immediately after 15 in sorted order

Step 1: Check if node 15 has right child

20 -> 10 -> 30 -> 15 ↑ -> null
Right child of 15: null

Why: If right child exists, successor is leftmost node in right subtree

Step 2: Since no right child, move up to parent 10 and check if 15 is left child

20 -> 10 ↑ -> 30 -> 15
15 is right child of 10

Why: Successor is first ancestor where node is in left subtree

Step 3: Move up to parent 20 and check if 10 is left child

20 ↑ -> 10 -> 30 -> 15
10 is left child of 20

Why: Found ancestor 20 where 10 is left child, so successor is 20

Result:

Successor of 15 is 20
BST state unchanged:
      20 ↑
     /  \
   10    30
     \     \
     15    40

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 leftmost(node):
    while node.left:
        node = node.left
    return node

def inorder_successor(node):
    # If right child exists, successor is leftmost in right subtree
    if node.right:
        return leftmost(node.right)
    # Else move up until node is left child of parent
    curr = node
    while curr.parent and curr == curr.parent.right:
        curr = curr.parent
    return curr.parent

# Driver code
root = None
for v in [20, 10, 30, 15, 40]:
    root = insert(root, v)

node = find_node(root, 15)
succ = inorder_successor(node)
if succ:
    print(f"Successor of {node.val} is {succ.val}")
else:
    print(f"No successor for {node.val}")

if node.right:

Check if node has right subtree to find successor there

return leftmost(node.right)

Successor is leftmost node in right subtree

while curr.parent and curr == curr.parent.right:

Move up until node is left child of its parent

return curr.parent

Return the parent which is the successor

Output

Successor of 15 is 20

Complexity Analysis

Time: O(h) because we traverse up or down the tree height h at most once

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

vs Alternative: Naive approach would do inorder traversal O(n) to find successor, this is faster using BST properties

Edge Cases

Node has right subtree

Successor is leftmost node in right subtree

DSA Python

if node.right:

Node has no right subtree and is left child

Successor is parent node

DSA Python

while curr.parent and curr == curr.parent.right:

Node is the largest (no successor)

Returns None indicating no successor

DSA Python

return curr.parent

When to Use This Pattern

When asked for the next bigger element in a BST, use the inorder successor pattern to find it efficiently by checking right subtree or moving up ancestors.

Common Mistakes

Mistake: Only checking right subtree and ignoring moving up to parent when no right child
Fix: Add loop to move up parents until node is left child of parent

Mistake: Not maintaining parent pointers in nodes
Fix: Store parent references during insertion to allow upward traversal

Summary

Finds the next node in sorted order after a given node in a BST.

Use when you need the immediate larger value than a given node in BST.

If right child exists, go right then leftmost; else go up until you find a node that is left child of its parent.

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