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. Consider the following code snippet implementing the optimal iterative approach to convert a BST to a Greater Tree. Given the BST with nodes [2, 1, 3], what is the value of the root node after the function completes?

easy

A. 5

B. 6

C. 3

D. 4

Solution

1. Step 1: Trace reverse inorder traversal order

   Nodes visited in order: 3, 2, 1.

2. Step 2: Accumulate sums and update nodes

   acc_sum=0 initially. - Visit 3: acc_sum=3, node.val=3 - Visit 2: acc_sum=3+2=5, node.val=5 - Visit 1: acc_sum=5+1=6, node.val=6 Root node was 2, updated to 5.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Root node value after update is 5 [OK]

Hint: Reverse inorder sums nodes from largest to smallest [OK]

Common Mistakes:

• Confusing traversal order and updating nodes too early
• Off-by-one errors in accumulating sums
• Misidentifying which node is root after updates

2. Given the following code for deleting a node in a BST, what is the value of root.val after calling deleteNode(root, 3) on the BST constructed by inserting nodes in order: 5, 3, 6?

easy

A. 6

B. 5

C. 3

D. null (root deleted)

Solution

1. Step 1: Construct BST and locate node 3

   BST: root=5, left=3, right=6. Node with value 3 is a leaf (no children).

2. Step 2: Delete node 3

   Since node 3 has no children, deletion returns null for root.left. Root remains 5 with left child null and right child 6.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Root value unchanged at 5 after deleting leaf 3 [OK]

Hint: Deleting leaf node returns null for that subtree [OK]

Common Mistakes:

• Confusing root with deleted node
• Replacing root value incorrectly
• Assuming root is deleted

3. Consider the following buggy code for inserting a value into a BST. Which line contains the subtle bug that causes the insertion to fail silently in some cases?

def insertIntoBST(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        insertIntoBST(root.left, val)
    else:
        insertIntoBST(root.right, val)
    return root

medium

A. Line 2: if root is None

B. Line 4: if val < root.val

C. Line 7: insertIntoBST(root.right, val)

D. Line 5: insertIntoBST(root.left, val)

Solution

1. Step 1: Analyze recursive calls

   Recursive calls to insertIntoBST on root.left or root.right do not update the parent's child pointer.

2. Step 2: Identify missing assignment

   Lines 5 and 7 call insertIntoBST but do not assign the returned subtree back to root.left or root.right, so insertion is lost.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing assignment causes silent insertion failure [OK]

Hint: Recursive insert must assign returned subtree to parent's child [OK]

Common Mistakes:

• Not updating parent's child pointer
• Confusing base case with recursive step
• Incorrect comparison operator

4. The following code attempts to search for a value in a BST. Identify the line containing the subtle bug that can cause incorrect behavior or inefficiency.

def searchBST(root, val):
    if root is None:
        return None
    if root.val == val:
        return root
    left_search = searchBST(root.left, val)
    if left_search is not None:
        return left_search
    return searchBST(root.right, val)

medium

A. Line 5: left_search = searchBST(root.left, val)

B. Line 4: if root.val == val: return root

C. Line 2: if root is None: return None

D. Line 7: return searchBST(root.right, val)

Solution

1. Step 1: Understand the code logic

   This code searches both left and right subtrees regardless of BST property.

2. Step 2: Identify inefficiency bug

   Line 5 always searches left subtree even if val > root.val, ignoring BST property and causing O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Ignoring BST property causes unnecessary subtree searches [OK]

Hint: Searching both subtrees ignores BST property [OK]

Common Mistakes:

• Not pruning search using BST property

5. The following code attempts to find if there exist two distinct nodes in a BST whose values sum to k. Identify the line containing the subtle bug that can cause incorrect results.

medium

A. Line 6: dfs(node.left)

B. Line 4: if k - node.val in seen:

C. Line 7: seen.add(node.val)

D. Line 8: dfs(node.right)

Solution

1. Step 1: Understand DFS and set usage

   The code checks if complement exists in seen before adding current node's value.

2. Step 2: Identify bug in order of operations

   Checking complement before adding current node's value misses pairs where both nodes are the same, or misses valid pairs if current node's value is needed for complement checks in children.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Complement check must happen after adding current node's value to seen [OK]

Hint: Add current node to set before checking complements [OK]

Common Mistakes:

• Checking complement before adding current node's value
• Not handling None nodes properly
• Returning False too early