DSA sheet · Trees · Binary Search Tree pattern

BST Iterator

This video teaches how to hand out the values of a binary search tree one at a time, in sorted order, without first copying the whole tree into a list. The teacher says it looks hard at first but is really easy once you see the trick: keep only the "left edge" of the tree in a stack, and grow it a little after every pop. This idea matters a lot, because later problems (like Two Sum IV and Kth Smallest) reuse this exact iterator to get an optimised answer.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: store the whole inorder first
• Part B · Optimal: a stack that holds only the left edge
• Part C · Revision page

Part 0 · Before starting

What is a tree node?

Each node is a small box with 3 things: its value, a link to its left child and a link to its right child. A missing child is None.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val       # the number in this node
        self.left = left     # left child, or None
        self.right = right   # right child, or None

What is a Binary Search Tree (BST)?

A BST is a binary tree with one extra promise, and it holds at every node:

• every value in its left subtree (the left child, plus everything below the left child) is smaller than the node;
• every value in its right subtree (the right child, plus everything below it) is bigger than the node.

Careful: it is all nodes below, not just the two children. In the tree below, 4 sits on the right of 3 (fine, 4 > 3), but it is also inside 7's left subtree, so it must be smaller than 7 too (it is).

            7
          /   \
         3     15
        / \    / \
       1   5  9   20
          / \
         4   6

This is the tree the teacher uses all through the video (we'll call it "the teacher's tree").

Inorder traversal, and why a BST gives sorted order

Inorder means: visit the left subtree fully, then the node itself, then the right subtree fully. The same rule repeats inside every subtree.

Why is it sorted for a BST? At any node, everything on its left is smaller and everything on its right is bigger. Inorder prints all the smaller ones first, then the node, then all the bigger ones. The same is true inside each subtree, so the whole output comes out smallest to largest.

For the teacher's tree: start at 7, keep going left to 3, then to 1 (a node with no left child). Print 1. Then 1's parent 3. Then 3's right subtree: inside it, left first (4), then 5, then 6. Then 7. Then 7's right subtree: 9, 15, 20.

What is a stack?

A stack is a pile: you add on top (append) and remove from the top (pop). The last thing you put in is the first thing that comes out (LIFO: last in, first out). In Python a plain list works as a stack.

What does "iterator" mean here?

An iterator is an object that gives you the items of a collection one by one when you ask. You don't get all items at once; each request gives you the next one.

Part A · Brute force: store the whole inorder first

LeetCode 173 · Binary Search Tree Iterator

1The question in simple words

Build a class BSTIterator with three pieces:

• BSTIterator(root), the constructor: it receives the root of a BST and sets things up. Think of an imaginary pointer that starts before the smallest value (on "nothing").
• next(): move the pointer one step forward and return the value there. So the 1st call returns the smallest value, the 2nd call returns the 2nd smallest, and so on. In other words, the values must come out in inorder.
• hasNext(): return True if there is still at least one value that next() hasn't returned yet, else False.

On the teacher's tree, repeated next() calls give 1, 3, 4, 5, 6, 7, 9, 15, 20.

2What the constraints tell us

• Number of nodes: 1 to 10⁵. With n = 10⁵, an O(n²) idea would be about 10¹⁰ steps, far above the ~10⁸ limit → TLE. So the total work must stay around O(n) or O(n log n).
• Values: 0 to 10⁶ → fits easily in a normal int (ints go up to about 2·10⁹). No overflow worries.
• At most 10⁵ calls in total to next and hasNext.
• Every next() call is guaranteed to be valid (there will always be a value to return when it's called).

3Intuition: just do the inorder once and read from it

The first idea that comes to mind: we know inorder of a BST is sorted. So in the constructor, do the full inorder traversal and save every value in a list. After that, each next() just reads the next item, and hasNext() just checks whether any items are left.

Think of it like printing the whole sorted list on a sheet of paper on day one, then reading one line every time someone asks.

4Building the logic

• Constructor: run an ordinary recursive inorder (left, node, right) and append each value. For the teacher's tree the list becomes [1, 3, 4, 5, 6, 7, 9, 15, 20].
• next(): return the value at the current position and move the position forward by one.
• hasNext(): the teacher's point: just look at the size. If there are still unread items, the answer is True.

5Approach steps

1. In the constructor, do an inorder traversal and save every value in self.vals. Set self.i = 0.
2. next(): take self.vals[self.i], add 1 to self.i, return the value.
3. hasNext(): return self.i < len(self.vals).

6Code (Python)

class BSTIterator:
    def __init__(self, root):
        self.vals = []
        self.i = 0                    # position of the next value to give
        self.inorder(root)

    def inorder(self, node):
        if node is None:
            return
        self.inorder(node.left)       # left
        self.vals.append(node.val)    # node
        self.inorder(node.right)      # right

    def next(self):
        val = self.vals[self.i]
        self.i += 1
        return val

    def hasNext(self):
        return self.i < len(self.vals)

7Code line by line

8Dry run

1. Constructor on the teacher's tree → vals = [1, 3, 4, 5, 6, 7, 9, 15, 20], i = 0.
2. next() → returns 1, i = 1. next() → 3, i = 2. next() → 4, i = 3.
3. hasNext() → 3 < 9 → True.
4. … six more next() calls give 5, 6, 7, 9, 15, 20, and i becomes 9.
5. hasNext() → 9 < 9 is false → False. Done.

9Complexity, and the teacher's "why not this?"

• Time: O(n) once in the constructor to fill the list. After that, each next() and hasNext() is O(1).
• Space: O(n), because every value is stored.

This is honestly a fine answer. But the teacher pushes us to think further:

• Suppose the tree has 10⁵ nodes, but the caller only makes two calls, say two next()s. We traversed and stored all 10⁵ values to answer just 2 questions. That's a lot of wasted work and memory.
• So the real question is: can we store only a little, just enough for the next answer, and fetch more only when someone asks? That's Part B.

Part B · Optimal: a stack that holds only the left edge

1The question (same as Part A)

Same class, same three methods. The goal now: don't store all n values. Store only what's needed to give the next answer.

2What the constraints tell us

• n up to 10⁵ and up to 10⁵ calls → overall work must stay about linear. No O(n²).
• LeetCode's follow-up asks for next() and hasNext() in average O(1) time using only O(h) memory, where h is the height of the tree (the number of levels on the longest path from the root down to a leaf). The approach below meets exactly that.

3Intuition: think about where the first answer is

We only have the root (7). The first next() must return the smallest value. In a BST the smallest value is the leftmost node: keep going left until there is no left child. On the teacher's tree: 7 → 3 → 1.

There's no way to reach 1 without passing 7 and 3. So we may as well keep them while walking down: save 7, then 3, then 1.

Now which one should come out first? 1, the one we saved last. "Last in, first out" is exactly a stack. So we push 7, 3, 1 onto a stack, and popping gives 1 first, then 3, then 7, which is the right order for these three.

How long did that first walk take? We went down one node per level, so it's about the height: around log n for a nicely balanced tree. But for a tree leaning to the left (a long chain of left children), it can be close to n.

4Building the rule from the example

Step 1: pop 1. Does 1 have a right child?

We pop 1 and return node.val = 1. Before returning, we look at 1's right child: there is none. So nothing new to push. The stack is now [7, 3].

Step 2: pop 3. Now the important moment

The next next() pops 3 and should return 3. Fine. But think about the call after that. Should it return 7 (the next thing on the stack)? Look at the inorder again: 1 3 4 5 6 7 …. After 3 comes 4, not 7. Why? Because inorder is left, node, right: after 3 itself, we must finish 3's right subtree (4, 5, 6) before going up to 7.

So when we pop 3, we must add 3's right subtree's nodes to the stack, on top of 7, before returning. How exactly? The same way we started from the root: start at the right child (5) and keep going left, pushing each one: push 5, then 4. Now the stack is [7, 5, 4] and 4 is on top, which is correct.

Why push only the left chain, and not the right children too?

Notice 5 also has a right child, 6. We did not push 6 yet. The teacher explains why with this picture: stand at 3's right child 5. Inorder needs 4 (left), then 5 (the node), then 6 (right). If we pushed 6 now, it would sit on the stack in the wrong place. We can only "unlock" a node's right side after that node itself has been popped.

Same thing on the other side of the tree: when 7 is popped, we go to 15 and push 15 and its left child 9. We do not push 20 yet, because 20 must come after 15, and 15 hasn't been given out yet. Only when 15 is popped do we get to push 20.

The helper: push_all

"Start at a node and keep pushing while going left" happens in two places (in the constructor with the root, and in next() with the popped node's right child). So the teacher writes it once as a helper and calls it from both places.

5Approach steps

1. Make an empty stack.
2. push_all(node): while node is not None, push node and move node = node.left.
3. Constructor: call push_all(root).
4. next(): pop the top node. Call push_all(node.right) (does nothing if there's no right child). Return node.val.
5. hasNext(): return True if the stack is not empty.

6Code (Python)

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self.push_all(root)           # root and its whole left chain

    def push_all(self, node):
        while node is not None:
            self.stack.append(node)   # push the NODE, not just the value
            node = node.left          # keep going left

    def next(self):
        node = self.stack.pop()       # smallest value not given yet
        self.push_all(node.right)     # unlock its right subtree's left chain
        return node.val

    def hasNext(self):
        return len(self.stack) > 0

7Code line by line

When the teacher first ran her code it failed because of one small missing piece; she added it and it passed. The usual culprits here: forgetting node = node.left in the loop, or forgetting to call push_all(root) in the constructor.

8Dry run: watch the stack at every step

The teacher's tree again, inorder 1 3 4 5 6 7 9 15 20. The left of each stack picture is the bottom, the red box is the top.

            7
          /   \
         3     15
        / \    / \
       1   5  9   20
          / \
         4   6

1. BSTIterator(root) → push_all(7): push 7, go left; push 3, go left; push 1, go left → None, stop.

1. next(): pop 1. 1 has no right child → push nothing. Return 1.

1. hasNext(): stack has 2 nodes → True. (Stack unchanged.)
2. next(): pop 3. 3 has right child 5 → push_all(5): push 5, go left; push 4, go left → None. Return 3.

1. next(): pop 4. No right child. Return 4.

1. next(): pop 5. 5 has right child 6 → push_all(6): push 6; 6 has no left → stop. Return 5.

1. next(): pop 6. No right child. Return 6. Now 3's whole right subtree (4, 5, 6) is done, and 7 is back on top, exactly as inorder wants.

1. next(): pop 7. 7 has right child 15 → push_all(15): push 15, go left; push 9, go left → None. (20 is not pushed.) Return 7.

1. next(): pop 9. No right child. Return 9.

1. next(): pop 15. 15 has right child 20 → push_all(20): push 20. Return 15.

1. hasNext(): one node left → True.
2. next(): pop 20. No right child. Return 20.

1. hasNext(): stack is empty → False. All 9 values came out in sorted order: 1 3 4 5 6 7 9 15 20 ✓

Look at the stack sizes: never more than 3, even though the tree has 9 nodes. The stack holds at most one node from each level, i.e. at most the height of the tree.

The teacher's space argument in numbers: if the caller made only one next() call, we stored just 7, 3, 1 (3 nodes) instead of all 9. After a second call, we've popped 3 and pushed 5 and 4, so still only 3 nodes. The brute force would have stored all 9 from the start.

9Complexity & remember

• Time, all calls together: O(n). Each node is pushed exactly once and popped exactly once over the whole life of the iterator. So the total work is the same as one normal inorder traversal, as the teacher says.
• Time per call: O(1) on average. One next() can be slow (e.g. popping 7 pushes a whole chain), but most calls push nothing. Spread over n calls, it averages to a constant. (This "averaged over many calls" cost is called amortised O(1).) hasNext() is always O(1).
• Space: O(h), the height. The teacher calls this "log n", which is true for a balanced tree. For a tree that is one long left chain, h = n, so the worst case is still O(n). The win is that we never store more than one path's worth of nodes, and we only store them when they're needed.

Part C · Revision page

root = TreeNode(7,
                TreeNode(3, TreeNode(1), TreeNode(5, TreeNode(4), TreeNode(6))),
                TreeNode(15, TreeNode(9), TreeNode(20)))
it = BSTIterator(root)
out = []
while it.hasNext():
    out.append(it.next())
print(out)            # [1, 3, 4, 5, 6, 7, 9, 15, 20]

it = BSTIterator(TreeNode(7, TreeNode(3), TreeNode(15, TreeNode(9), TreeNode(20))))
print(it.next(), it.next(), it.hasNext())   # 3 7 True

Based on this video: Binary Search Tree Iterator