BST Inorder Successor in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find the inorder successor of a node with right subtree

What is the output of the code when finding the inorder successor of node 15 in the given BST?

DSA Python

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

def inorder_successor(root, p):
    successor = None
    while root:
        if p.val < root.val:
            successor = root
            root = root.left
        else:
            root = root.right
    return successor.val if successor else None

# Construct BST
root = Node(20)
root.left = Node(10)
root.right = Node(30)
root.left.left = Node(5)
root.left.right = Node(15)
root.left.right.left = Node(13)
root.left.right.right = Node(17)

p = root.left.right  # Node with value 15
print(inorder_successor(root, p))

A 17

B 20

C 13

D None

💡 Hint

Remember, if the node has a right child, the successor is the leftmost node in the right subtree.

The inorder successor of node 15 is the smallest node in its right subtree, which is 17.

❓ Predict Output

intermediate

Find the inorder successor of a node without right subtree

What is the output of the code when finding the inorder successor of node 17 in the given BST?

DSA Python

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

def inorder_successor(root, p):
    successor = None
    while root:
        if p.val < root.val:
            successor = root
            root = root.left
        else:
            root = root.right
    return successor.val if successor else None

# Construct BST
root = Node(20)
root.left = Node(10)
root.right = Node(30)
root.left.left = Node(5)
root.left.right = Node(15)
root.left.right.left = Node(13)
root.left.right.right = Node(17)

p = root.left.right.right  # Node with value 17
print(inorder_successor(root, p))

A 30

B None

C 15

D 20

💡 Hint

If the node has no right child, the successor is one of its ancestors.

Node 17 has no right child, so the successor is the lowest ancestor whose left child is also an ancestor of 17, which is 20.

🔧 Debug

advanced

Identify the error in inorder successor code

What error does the following code raise when trying to find the inorder successor of node 30?

DSA Python

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

def inorder_successor(root, p):
    if p.right:
        curr = p.right
        while curr.left:
            curr = curr.left
        return curr.val
    successor = None
    while root:
        if p.val < root.val:
            successor = root
            root = root.left
        else:
            root = root.right
    return successor.val

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

p = root.right  # Node with value 30
print(inorder_successor(root, p))

A No error, outputs 15

B NoneType has no attribute 'val'

C AttributeError

D TypeError

💡 Hint

Check what happens if successor remains None before accessing successor.val.

If the node has no right subtree and no successor found, successor remains None, so accessing successor.val raises an AttributeError.

🧠 Conceptual

advanced

Inorder successor in BST with parent pointers

Given a BST where each node has a parent pointer, which of the following is the correct logic to find the inorder successor of a node p?

A Successor is always the parent node regardless of children.

B If p has left child, successor is rightmost node in left subtree; else move up until node is right child of its parent, then parent is successor.

C If p has right child, successor is leftmost node in right subtree; else move up until node is left child of its parent, then parent is successor.

D If p has right child, successor is rightmost node in right subtree; else successor is leftmost node in left subtree.

💡 Hint

Think about inorder traversal order and how parent pointers help.

The inorder successor is the next node visited after p in inorder traversal. If p has a right child, it's the leftmost node in that subtree. Otherwise, move up using parent pointers until you find a node that is a left child of its parent; that parent is the successor.

🚀 Application

expert

Count nodes with no inorder successor in BST

Given a BST, how many nodes have no inorder successor? Consider the BST below: 20 / \ 10 30 / \ \ 5 15 40 17 Select the correct count.

A 1

B 4

C 3

D 2

💡 Hint

The node with no inorder successor is the largest node in the BST.

Only node 40 has no inorder successor because it is the largest node in the BST.

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