BST Inorder Successor in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the left child of a node in a BST.

DSA Python

def left_child(node):
    return node.[1]

Drag options to blanks, or click blank then click option'

Aright

Bleft

Cparent

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'right' instead of 'left' to access the left child.

The left child of a node is accessed using node.left.

2fill in blank

medium

Complete the code to find the minimum node in a BST subtree.

DSA Python

def find_min(node):
    current = node
    while current.[1] is not None:
        current = current.left
    return current

Drag options to blanks, or click blank then click option'

Avalue

Bright

Cparent

Dleft

Attempts:

3 left

💡 Hint

Common Mistakes

Checking right child instead of left child.

To find the minimum node, we keep going to the left child until it is None.

3fill in blank

hard

Fix the error in the code to find the inorder successor when the node has no right child.

DSA Python

def inorder_successor(node):
    if node.right:
        return find_min(node.right)
    parent = node.[1]
    while parent and node == parent.right:
        node = parent
        parent = parent.parent
    return parent

Drag options to blanks, or click blank then click option'

Avalue

Bright

Cparent

Dleft

Attempts:

3 left

💡 Hint

Common Mistakes

Using left or right instead of parent to move up.

To move up the tree, we use the parent attribute.

4fill in blank

hard

Fill both blanks to complete the code that finds the inorder successor of a node in a BST.

DSA Python

def inorder_successor(node):
    if node.right:
        return find_min(node.[1])
    parent = node.[2]
    while parent and node == parent.right:
        node = parent
        parent = parent.parent
    return parent

Drag options to blanks, or click blank then click option'

Aright

Bleft

Cparent

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Using left child instead of right for the first blank.

Using left or right instead of parent for the second blank.

The successor is the minimum node in the right subtree, so use right. If no right child, move up using parent.

5fill in blank

hard

Fill all three blanks to complete the code that returns the inorder successor's value or None if no successor.

DSA Python

def inorder_successor_value(node):
    successor = None
    if node.[1]:
        successor = find_min(node.[2])
    else:
        parent = node.[3]
        while parent and node == parent.right:
            node = parent
            parent = parent.parent
        successor = parent
    return successor.value if successor else None

Drag options to blanks, or click blank then click option'

Aright

Cparent

Dleft

Attempts:

3 left

💡 Hint

Common Mistakes

Using left child instead of right for the first two blanks.

Using left or right instead of parent for the third blank.

If the node has a right child, the successor is the minimum node in the right subtree (right). Otherwise, move up using 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