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 for finding the kth smallest element in a BST, what is the returned value when called with k=2 on the provided tree?

from typing import Optional

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

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    stack = []
    current = root
    count = 0

    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        count += 1
        if count == k:
            return current.val
        current = current.right

# Tree:
#     3
#    / \
#   1   4
#    \
#     2

root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kthSmallest(root, 2))

easy

A. 3

B. 1

C. 2

D. 4

Solution

1. Step 1: Trace the inorder traversal steps

   Stack initially empty, current=root(3). Push 3, move left to 1. Push 1, move left to None. Pop 1 (count=1), move right to 2.

2. Step 2: Continue traversal to find kth=2

   Push 2, move left None. Pop 2 (count=2), return 2 as kth smallest.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Second smallest in BST is 2 [OK]

Hint: Inorder traversal visits nodes in ascending order [OK]

Common Mistakes:

• Off-by-one counting of k
• Returning before incrementing count

2. You are given a binary tree where each node has a unique integer value. You need to find whether a given value exists in the tree efficiently by leveraging the tree's ordering properties. Which approach guarantees the fastest search in the worst case?

easy

A. Use the BST property to decide whether to search left or right subtree at each node, recursively or iteratively.

B. Perform a breadth-first search (BFS) to find the value level by level.

C. Traverse the entire tree recursively checking each node until the value is found.

D. Use dynamic programming to store previously searched subtrees to avoid repeated work.

Solution

1. Step 1: Understand the problem constraints

   The tree is a BST, so left subtree nodes are less than the node, right subtree nodes are greater.

2. Step 2: Identify the optimal search approach

   Using the BST property allows skipping half of the tree at each step, leading to O(h) time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BST property guides search direction efficiently [OK]

Hint: BST property enables directed search, not full traversal [OK]

Common Mistakes:

• Thinking BFS or full traversal is optimal for BST search

3. Examine the following code snippet intended to balance a BST by collecting nodes via inorder traversal and rebuilding the tree. Identify the subtle bug that could cause incorrect tree structure or cycles.

medium

A. The left and right pointers of nodes are not reset before rebuilding.

B. The inorder traversal appends nodes instead of values.

C. The middle index calculation uses integer division which may skew balance.

D. The stack is popped instead of dequeued, reversing processing order.

Solution

1. Step 1: Identify pointer reset necessity

   When rebuilding, left and right pointers must be reset to avoid old links causing cycles.

2. Step 2: Locate missing reset in code

   Commented out line resetting node.left and node.right causes bug.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Not resetting pointers -> cycles or incorrect tree [OK]

Hint: Always reset node pointers when rebuilding trees [OK]

Common Mistakes:

• Ignoring pointer reset leads to subtle bugs
• Misunderstanding traversal appending nodes is correct
• Thinking stack order affects correctness here

4. The following code attempts to compute the range sum of a BST using iterative DFS with pruning. Identify the line containing the subtle bug that causes incorrect results or inefficiency.

medium

A. Line that appends node.left when node.val < low

B. Line that pops node from stack

C. Line that adds node.val to total

D. Line that appends node.right when node.val is in range

Solution

1. Step 1: Understand pruning logic

   If node.val < low, left subtree nodes are smaller and cannot be in range, so left subtree should be skipped.

2. Step 2: Identify incorrect line

   Appending node.left when node.val < low causes unnecessary traversal of left subtree, violating pruning. It should append node.right instead.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct pruning requires appending node.right only when node.val < low [OK]

Hint: Prune left subtree if node.val < low [OK]

Common Mistakes:

• Appending wrong subtree when pruning
• Forgetting to check null nodes

5. What is the time complexity of the optimal iterative pruning algorithm for trimming a BST with n nodes, and why?

medium

A. O(log n), because pruning skips entire subtrees quickly.

B. O(n^2), because nested loops may cause repeated visits to nodes.

C. O(n log n), because each pruning step may traverse log n nodes repeatedly.

D. O(n), because each node is visited at most once during pruning.

Solution

1. Step 1: Analyze root adjustment loop

   Root moves down skipping invalid nodes, each step moves to a child, total O(n) in worst case.

2. Step 2: Analyze left and right subtree trimming loops

   Each inner loop removes invalid children by pointer reassignment, each node visited once overall.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Each node processed once, total O(n) time [OK]

Hint: Each node visited once despite nested loops [OK]

Common Mistakes:

• Assuming pruning is O(log n) due to BST
• Confusing nested loops as O(n^2)