BST Iterator (In-Order Next)

▶

Steps

setup

Initialize Iterator with root node

The iterator is initialized with the root node (7). The current pointer is set to root, and _advance() is called to find the first next_val.

💡 Initialization sets up the traversal starting point and prepares the first next value for immediate retrieval.

Line:

self.current = root
self.next_val = None
self._advance()

💡 The iterator is ready to start traversal from the root, with next_val unset until _advance finds the first node.

compare

Check if current node (7) has left child

The algorithm checks if current node 7 has a left child. Since it does (node 3), it proceeds to find the inorder predecessor.

💡 This check determines whether to visit current immediately or to explore left subtree first.

Line:

if not self.current.left:

💡 Nodes with left children require threading to traverse left subtree first.

traverse

Find inorder predecessor of current (7)

Set pre to current.left (node 3). Since pre.right is null, this is the inorder predecessor.

💡 Finding the rightmost node in left subtree allows threading to return after left subtree is done.

Line:

pre = self.current.left
while pre.right and pre.right != self.current:
    pre = pre.right

💡 The predecessor's right pointer is used as a temporary thread to current.

expand

Create thread from predecessor (3) to current (7)

Since pre.right is null, set pre.right to current (7) to create a thread, then move current to current.left (3).

💡 Threading allows returning to current node after finishing left subtree without stack.

Line:

if not pre.right:
    pre.right = self.current
    self.current = self.current.left

💡 The tree is temporarily modified to enable O(1) space traversal.

fill_cells

Current node (3) has no left child, visit it

Since current node 3 has no left child, visit it by setting next_val to 3, then move current to its right child (which is the thread back to 7).

💡 Visiting nodes without left children is straightforward and yields the next smallest element.

Line:

if not self.current.left:
    self.next_val = self.current.val
    self.current = self.current.right
    return

💡 Nodes without left children are the next in in-order sequence.

traverse

Call next(): return 3 and advance

The next() call returns the current next_val (3). Then _advance() is called to find the next next_val.

💡 Each next() returns the next smallest element and prepares the following one.

Line:

val = self.next_val
self._advance()
return val

💡 The iterator maintains the next value ready for immediate return.

traverse

Find predecessor of current (7) again

Current is 7 again. Find its inorder predecessor (3) by following left child and then right pointers until pre.right is current (thread).

💡 Detecting the thread indicates left subtree is done and current can be visited.

Line:

pre = self.current.left
while pre.right and pre.right != self.current:
    pre = pre.right

💡 Thread presence signals to revert it and visit current.

shrink

Remove thread and visit current (7)

Since pre.right points to current, revert it to null to remove the thread. Visit current by setting next_val to 7, then move current to its right child (15).

💡 Removing the thread restores the original tree structure and allows visiting current node.

Line:

else:
    pre.right = None
    self.next_val = self.current.val
    self.current = self.current.right
    return

💡 Threading is temporary and undone after use to preserve tree.

traverse

Call next(): return 7 and advance

The next() call returns 7 and calls _advance() to find the next next_val.

💡 Each next() call returns the prepared next_val and triggers finding the next smallest.

Line:

val = self.next_val
self._advance()
return val

💡 The iterator maintains a ready next_val for efficient retrieval.

compare

Current (15) has left child (9), find predecessor

Current node 15 has left child 9. Find predecessor by moving to 9 and checking right pointers. 9 has no right child, so it is predecessor.

💡 Finding predecessor prepares for threading to traverse left subtree first.

Line:

if not self.current.left:
    ...
else:
    pre = self.current.left
    while pre.right and pre.right != self.current:
        pre = pre.right

💡 Threading enables traversal without stack or recursion.

expand

Create thread from predecessor (9) to current (15)

Since pre.right is null, set pre.right to current (15) to create a thread, then move current to current.left (9).

💡 Threading allows returning to current after left subtree traversal.

Line:

if not pre.right:
    pre.right = self.current
    self.current = self.current.left

💡 Temporary modification enables O(1) space traversal.

fill_cells

Current (9) has no left child, visit it

Current node 9 has no left child, so visit it by setting next_val to 9, then move current to right child (thread back to 15).

💡 Visiting nodes without left children yields next smallest element.

Line:

if not self.current.left:
    self.next_val = self.current.val
    self.current = self.current.right
    return

💡 Nodes without left children are next in in-order.

traverse

Call next(): return 9 and advance

The next() call returns 9 and calls _advance() to find the next next_val.

💡 Each next() returns the next smallest element and prepares the next one.

Line:

val = self.next_val
self._advance()
return val

💡 The iterator maintains next_val for efficient retrieval.

traverse

Find predecessor of current (15) again

Current is 15 again. Find predecessor (9) by following left child and right pointers. Pre.right points to current, so thread exists.

💡 Thread presence signals left subtree done and current ready to visit.

Line:

pre = self.current.left
while pre.right and pre.right != self.current:
    pre = pre.right

💡 Threading is temporary and removed after use.

shrink

Remove thread and visit current (15)

Remove thread by setting pre.right to null. Visit current by setting next_val to 15, then move current to right child (20).

💡 Removing thread restores tree and allows visiting current node.

Line:

else:
    pre.right = None
    self.next_val = self.current.val
    self.current = self.current.right
    return

💡 Threading is a temporary traversal aid.

traverse

Call next(): return 15 and advance

The next() call returns 15 and calls _advance() to find the next next_val.

💡 Each next() returns the next smallest element and prepares the next one.

Line:

val = self.next_val
self._advance()
return val

💡 The iterator maintains next_val for efficient retrieval.

fill_cells

Current (20) has no left child, visit it

Current node 20 has no left child, so visit it by setting next_val to 20, then move current to right child (null).

💡 Visiting nodes without left children yields next smallest element.

Line:

if not self.current.left:
    self.next_val = self.current.val
    self.current = self.current.right
    return

💡 Nodes without left children are next in in-order.

traverse

Call next(): return 20 and advance

The next() call returns 20 and calls _advance(), which finds current is null and sets next_val to None, indicating no more elements.

💡 When current is null, traversal is complete and hasNext() will return false.

Line:

val = self.next_val
self._advance()
return val

💡 Traversal ends when current is null and next_val is None.

compare

Call hasNext(): check if next_val is not None

hasNext() returns true if next_val is not None, false otherwise. Currently next_val is None, so hasNext() returns false.

💡 hasNext() tells if more elements remain to be iterated.

Line:

return self.next_val is not None

💡 Iterator signals completion when no next_val is available.

class BSTIterator:
    def __init__(self, root):
        self.current = root  # STEP 1
        self.next_val = None
        self._advance()  # STEP 1

    def _advance(self):
        while self.current:  # STEP 2,3,7,10,14
            if not self.current.left:  # STEP 5,12,17
                self.next_val = self.current.val  # STEP 5,12,17
                self.current = self.current.right  # STEP 5,12,17
                return
            else:
                pre = self.current.left  # STEP 3,7,10,14
                while pre.right and pre.right != self.current:  # STEP 3,7,10,14
                    pre = pre.right
                if not pre.right:  # STEP 4,11
                    pre.right = self.current
                    self.current = self.current.left
                else:  # STEP 8,15
                    pre.right = None
                    self.next_val = self.current.val
                    self.current = self.current.right
                    return
        self.next_val = None  # STEP 18

    def next(self):
        val = self.next_val  # STEP 6,9,13,16,18
        self._advance()
        return val

    def hasNext(self):
        return self.next_val is not None  # STEP 19

📊

BST Iterator (In-Order Next) - Watch the Algorithm Execute, Step by Step

Watching this step-by-step reveals how the iterator efficiently finds the next smallest element by temporarily modifying the tree structure, which is hard to grasp from code alone.

Current node: 1

7315920

DFS Stack

1 (entered)

Current node: 1

7315920

DFS Stack

1 (entered)pre=null

Current node: 1

7315920

DFS Stack

1 (entered)pre=2

Current node: 2

7315920

DFS Stack

2 (entered)

Current node: 1

7315920

Current node: 1

7315920

DFS Stack

1 (entered)

Return: 3

Current node: 1

7315920

DFS Stack

1 (entered)pre=2

Current node: 3

7315920

Current node: 3

7315920

DFS Stack

3 (entered)

Return: 7

Current node: 3

7315920

DFS Stack

3 (entered)pre=4

Current node: 4

7315920

DFS Stack

4 (entered)

Current node: 3

7315920

Current node: 3

7315920

DFS Stack

3 (entered)

Return: 9

Current node: 3

7315920

DFS Stack

3 (entered)pre=4

Current node: 5

7315920

Current node: 5

7315920

DFS Stack

5 (entered)

Return: 15

7315920

7315920

Return: 20

7315920

Return: false

Key Takeaways

✓ Morris traversal uses temporary threads to traverse BST in-order without extra space.

This is hard to see from code alone because the tree is modified and restored dynamically.

✓ The iterator always keeps the next smallest element ready in next_val for O(1) next() calls.

Understanding this precomputation clarifies why next() is efficient and immediate.

✓ Thread creation and removal correspond to moving down left subtrees and returning to parent nodes.

Seeing these steps visually reveals the traversal order and how the algorithm avoids recursion or stack.

Practice

1. Given the following code snippet for converting a sorted array to a height-balanced BST, what is the value of the root node's value after the first call to helper with input nums = [1, 3, 5]?

easy

A. 3

B. 1

C. 5

D. None

Solution

1. Step 1: Calculate mid index for initial call

   For nums=[1,3,5], left=0, right=2, mid=(0+2)//2=1.

2. Step 2: Identify root value

   nums[mid] = nums[1] = 3, so root node value is 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mid index calculation picks 3 as root [OK]

Hint: Mid index picks middle element as root [OK]

Common Mistakes:

• Choosing first or last element as root
• Off-by-one mid calculation

2. You are given a binary search tree and a key. You need to remove the node with this key while maintaining the BST property. Which approach guarantees the correct and efficient deletion in all cases, including nodes with two children?

easy

A. Use a greedy approach that always deletes the node by replacing it with its left child, ignoring the right subtree.

B. Perform a breadth-first traversal to find and remove the node, then rebuild the tree from scratch.

C. Use a recursive approach that finds the node, then if it has two children, replace it with its in-order successor and recursively delete the successor.

D. Use dynamic programming to store subtrees and delete nodes based on precomputed results.

Solution

1. Step 1: Understand BST deletion cases

   Deletion must handle three cases: leaf node, node with one child, and node with two children. The two children case requires replacing the node with its in-order successor or predecessor to maintain BST properties.

2. Step 2: Identify approach that handles all cases correctly

   The recursive approach that finds the node, replaces it with its in-order successor if it has two children, and recursively deletes the successor ensures correctness and efficiency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Only Use a recursive approach that finds the node, then if it has two children, replace it with its in-order successor and recursively delete the successor. correctly handles all deletion cases preserving BST [OK]

Hint: Two-children deletion requires successor replacement [OK]

Common Mistakes:

• Greedy deletion ignoring right subtree breaks BST
• Rebuilding tree is inefficient
• Dynamic programming irrelevant here

3. What is the time complexity of the optimal solution that uses inorder traversal followed by the two-pointer technique to solve the Two Sum IV in BST problem, assuming the BST has n nodes?

medium

A. O(n log n) due to sorting the inorder traversal array

B. O(n^2) because two-pointer approach checks all pairs in worst case

C. O(n) because inorder traversal and two-pointer scan each take linear time

D. O(log n) because BST properties reduce search space

Solution

1. Step 1: Analyze inorder traversal time

   Inorder traversal visits each node once, O(n) time.

2. Step 2: Analyze two-pointer scan time

   Two pointers move inward at most n steps total, O(n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both steps are linear, total O(n) time [OK]

Hint: Inorder + two-pointer each O(n), total O(n) [OK]

Common Mistakes:

• Assuming sorting is needed after inorder traversal
• Confusing two-pointer with nested loops
• Thinking BST reduces complexity to log n

4. Suppose the input array can contain duplicate values and you want to build a height-balanced BST that allows duplicates on the right subtree. Which modification to the optimal approach is correct?

hard

A. Change mid calculation to always pick the left middle element to ensure duplicates go to the right subtree.

B. Change the recursive calls to insert duplicates always into the left subtree to maintain balance.

C. Keep mid calculation as is, but when inserting duplicates, always place them in the right subtree during tree construction.

D. Use the brute force approach inserting elements one by one to handle duplicates correctly.

Solution

1. Step 1: Understand duplicate handling

   Duplicates should be consistently placed in the right subtree to maintain BST property.

2. Step 2: Modify insertion logic

   Keep mid calculation unchanged for balance; during node creation, ensure duplicates go to right subtree by design.

3. Step 3: Avoid brute force

   Brute force insertion leads to unbalanced trees and higher complexity.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Maintain balance and BST property by consistent duplicate placement right [OK]

Hint: Keep mid; place duplicates right during construction [OK]

Common Mistakes:

• Changing mid breaks balance
• Inserting duplicates left breaks BST property

5. Suppose the BST can contain duplicate values, and you want to find all nodes with a given value. Which modification to the optimal iterative search algorithm correctly finds all such nodes?

hard

A. Stop at the first found node and return it, since duplicates are not allowed in BSTs.

B. Modify the search to continue searching both left and right subtrees even after finding a matching node.

C. Traverse the entire tree recursively to collect all nodes with the target value, ignoring BST property.

D. Use a queue to perform BFS and collect all nodes with the target value efficiently.

Solution

1. Step 1: Understand duplicates in BST

   Duplicates can appear on either left or right subtree depending on BST definition.

2. Step 2: Modify search to find all matches

   After finding a node with val, continue searching both subtrees to find all duplicates.

3. Step 3: Avoid full traversal

   Using BST property to prune search still possible by checking subtrees where duplicates may exist.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Continuing search after first match finds all duplicates [OK]

Hint: Duplicates require searching both subtrees after match [OK]

Common Mistakes:

• Stopping at first match or ignoring BST property completely