Binary Search Tree Iterator

Medium#173in-order

Design an iterator over a binary search tree. It is built from the root; next() returns the next value in increasing order, and hasNext() says whether any value is left. Both should take O(1) time on average and O(h) memory, where h is the height of the tree. Our tree: 12 with children 5 and 17; 5 has a right child, 9; 17 has a left child, 14. Our calls: BSTIterator(root), next(), next(), next(), hasNext(), next(), next(), hasNext() — they return 5, 9, 12, true, 14, 17, false.

173 Binary Search Tree IteratorWalkthrough · 1×

Example: BSTIterator(root), next(), next(), next(), hasNext(), next(), next(), hasNext() on a binary search tree: in-order with a stack, one value per call.

nonenonenonenonenonenone12517914next()returned—stacktop on the right—
not reached yeton the stacknodepopped, next() returns itgiven by next(), #n is its turnnone: an empty child

BSTIterator(root), root = 12

01/48
restart · back · play · step
Speed
1class BSTIterator:
2 function init(root):
3 stack = []
4 pushLeft(root)
5 function next():
6 node = stack.pop()
7 pushLeft(node.right)
8 return node.val
9 function hasNext():
10 return stack is not empty
11 function pushLeft(node):
12 while node is not none:
13 stack.push(node)
14 node = node.left
state
node
–
stack
[]
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The stack holds exactly the nodes in-order still owes: each one waits below the nodes of its left subtree, so the top is always the smallest value not given yet.
  2. After next() pops a node, the values right after it are in its right subtree, smallest first down its left side; pushLeft puts them on top, above the node's ancestors that come later.
  3. Every node is pushed and popped once over all calls, so next() is O(1) on average even when one call pushes a whole path.

Complexity

Time O(1) on average per call: n pushes and n pops spread over n calls of next(); hasNext() is O(1). Memory O(h): the stack holds at most one path from the root.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.