Binary Search Tree Iterator

Medium Trees & BST BST Basics Original on LeetCode

Reported atMetaAdobeCRED

Binary Search Tree Iterator is a medium trees & bst problem solved with the bst basics pattern. The best approach, optimal (controlled stack of the left spine), runs in O(1) amortized per call time and O(h) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (flatten in-order into a list) up.

Problem

Design a class BSTIterator that walks a binary search tree in ascending order, one value at a time.

  • BSTIterator(TreeNode root) sets up the iterator for the tree rooted at root. Conceptually, it starts just before the smallest value.
  • int next() moves to the next value in ascending order and returns it.
  • boolean hasNext() returns true if at least one value has not been returned yet.

next is only called when a value remains. The values returned by repeated next calls are exactly the in-order traversal of the tree.

Examples

Example 1

Input
BSTIterator([6,2,9,null,4]), next(), next(), hasNext(), next(), next(), hasNext()
Output
2, 4, true, 6, 9, false
Why
The in-order sequence of the tree is 2, 4, 6, 9; after four calls to next it is used up.

Example 2

Input
BSTIterator([3]), hasNext(), next(), hasNext()
Output
true, 3, false
Why
A single-node tree yields one value.

Constraints

  • The tree has between 1 and 10^5 nodes, and it is a valid binary search tree.
  • 0 <= Node.val <= 10^6
  • At most 10^5 calls are made in total, and next is only called when a value remains.
  • Aim for next and hasNext in O(1) amortized time with O(h) extra memory (h = tree height).

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (flatten in-order into a list)O(n) constructor, O(1) per callO(n)
Optimal (controlled stack of the left spine)O(1) amortized per callO(h)

1Brute force (flatten in-order into a list)

TimeO(n) constructor, O(1) per callThe full traversal happens up front; each call is then an index lookup.
SpaceO(n)Every value of the tree is copied into the list.

In the constructor, run an in-order traversal and store every value in a list. Keep an index into it: next returns the value at the index and advances it, and hasNext checks whether the index is still inside the list.

  1. Constructor: inorder(root) appends values to a list; idx = 0.
  2. next(): return values[idx++].
  3. hasNext(): return idx < values.size().
class BSTIterator {
    private final List<Integer> values = new ArrayList<>();
    private int idx = 0;

    public BSTIterator(TreeNode root) {
        inorder(root);
    }

    private void inorder(TreeNode node) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = node;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            values.add(cur.val);
            cur = cur.right;
        }
    }

    public int next() {
        return values.get(idx++);
    }

    public boolean hasNext() {
        return idx < values.size();
    }
}

2Optimal (controlled stack of the left spine)

TimeO(1) amortized per callEvery node is pushed and popped exactly once over all n calls to next, so the total work is O(n).
SpaceO(h)The stack holds at most one root-to-leaf path.

Run the iterative in-order traversal one step at a time. The stack always holds the path of nodes whose value has not been returned yet, smallest on top. next pops the top node; if it has a right child, push that child and all of its left descendants. hasNext is just "is the stack non-empty".

  1. pushLeft(node): while node != null, push it and go left.
  2. Constructor: pushLeft(root).
  3. next(): node = pop(); pushLeft(node.right); return node.val.
  4. hasNext(): return the stack is not empty.
class BSTIterator {
    private final Deque<TreeNode> stack = new ArrayDeque<>();

    public BSTIterator(TreeNode root) {
        pushLeft(root);
    }

    private void pushLeft(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }

    public int next() {
        TreeNode node = stack.pop();
        pushLeft(node.right);
        return node.val;
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }
}

Edge cases to test

  • A single node
  • A tree that is a chain to the left (h = n) or to the right
  • Calling hasNext several times in a row (it must not consume a value)

Hints

Hint 1

The values must come out in sorted order, which for a BST is the in-order traversal.

Hint 2

Flattening the whole traversal into a list works but uses O(n) memory. Can you produce it lazily?

Hint 3

Simulate iterative in-order traversal: keep a stack of the left spine. next pops a node, then pushes the left spine of its right child.

FAQ

What is the best time complexity for Binary Search Tree Iterator?

Optimal (controlled stack of the left spine) runs in O(1) amortized per call time and O(h) extra space. Every node is pushed and popped exactly once over all n calls to next, so the total work is O(n).

Which pattern does Binary Search Tree Iterator use?

It is a trees & bst problem that uses the bst basics pattern. Other problems with the same pattern: Search in a Binary Search Tree, Minimum element in BST, Insert into a Binary Search Tree.

Is there a brute force solution for Binary Search Tree Iterator?

Yes. Brute force (flatten in-order into a list) takes O(n) constructor, O(1) per call time and O(n) space. In the constructor, run an in-order traversal and store every value in a list.

Which edge cases should I test for Binary Search Tree Iterator?

A single node; A tree that is a chain to the left (h = n) or to the right; Calling hasNext several times in a row (it must not consume a value).