cf.completefrontend
TREES & TRIES · CORE

Iterative tree traversal with a stack

Walk a tree depth-first with a loop and your own stack, instead of a function that calls itself.

Time O(n)Space O(h)4 practice problemsStep-through picture

The idea

A recursive tree walk is short, but each call waits on the call stack until its children are done. On a very deep tree the call stack can run out of room and the program crashes. A loop with your own stack does the same walk without that limit.

A stack is a list where you add and remove only at the end: the last item added is the first one taken out. In JavaScript an array works: push adds to the end and pop removes from the end.

For an inorder walk (left subtree, then the node, then the right subtree), the idea is: go left as far as you can, pushing each node you pass. When you can't go left, pop the top node, record it, and move into its right subtree. Repeat until there is nothing left to visit.

An everyday example

Reading a stack of nested folders

You open a folder and see a subfolder on the left side. Before opening it, you drop a sticky note for the current folder on a pile on your desk. You keep going left and adding notes. When a folder has no left subfolder, you read its own papers, take its note off the top of the pile, and then open its right subfolder. The pile always tells you exactly where to return, in the right order.

How the example maps to the code
In the exampleIn the code
The pile of sticky notesstack
Adding a note before going leftstack.push(node); node = node.left;
Taking the top note off the pilenode = stack.pop()
Reading the folder's own papersresult.push(node.val)
Opening the right subfoldernode = node.right

From the slow way to iterative tree traversal with a stack

  1. The recursive inorder walk is three lines, but every call waits on the call stack, a small area of memory the engine uses to remember unfinished function calls. A tree built from a long reply thread can be 50,000 levels deep, and the recursive walk crashes with a RangeError long before it finishes.
  2. Look at what those waiting calls remember. A call on node is paused at one spot: it has gone into node.left and is waiting to record node and then go right. So the call stack is just a list of nodes whose left side is in progress, with the most recent one on top.
  3. We can keep that list ourselves in an ordinary array, stack, which can grow far larger than the call stack. Going down to the left replaces each recursive call: stack.push(node) and then node = node.left. When node becomes null, there is no more left side, which is the moment a recursive call would return.
  4. Returning becomes stack.pop(). The top node's left side is finished, so record it, then do what the recursive version does next: move into node.right and start going left again from there. Repeat while there is a subtree to enter or a node waiting. That loop is iterative inorder traversal.

How it works

  1. Start with an empty stack and node = root.
  2. Loop while node is not null or the stack still has nodes.
  3. Go left as far as possible: push node and move to node.left, until node is null.
  4. Pop the top of the stack. Its left subtree is done, so record its value in result.
  5. Move to its right subtree: node = node.right. The loop then goes left from there.
  6. When both node is null and the stack is empty, every node has been recorded.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function inorderIterative(root) {
  2. const result = [];
  3. const stack = [];
  4. let node = root;
  5. while (node !== null || stack.length > 0) {
  6. while (node !== null) {
  7. stack.push(node);
  8. node = node.left;
  9. }
  10. node = stack.pop();
  11. result.push(node.val);
  12. node = node.right;
  13. }
  14. return result;
  15. }

How fast it is

TimeO(n)
Extra memoryO(h)

Each node is pushed and popped once. The stack holds one path from the root at most, which is the tree's height h.

  • Best caseO(n)

    Any tree of n nodes. Every node must be pushed and popped once.

  • Average caseO(n)

    A random search tree: 2n stack steps, plus one check per empty child.

  • Worst caseO(n)

    A chain leaning left with 50,000 nodes. The time is still O(n), and the stack grows to 50,000 entries, which fits easily in normal memory where a recursive walk would overflow.

Common mistakes

  • Writing the loop as while (stack.length > 0) only. At the start the stack is empty, and after moving right node may be set while the stack is empty, so the walk stops early. Check both node and the stack.
  • In preorder, pushing the left child before the right child. The right child is then popped first and the order is wrong.
  • Forgetting node = node.right after recording. The loop then pops the same parents again or never reaches right subtrees.
  • Pushing null children in the preorder version and then reading .val of null. Only push children that exist.

When to use it

Look for these clues in a problem:

  • The tree can be very deep (tens of thousands of levels), so recursion may overflow the call stack.
  • You want to pause the walk and continue later, like an iterator with a next() method.
  • You want to stop early, such as after the k-th node in sorted order, without unwinding recursion.
  • The problem says "without recursion" or "using O(h) memory".

Check yourself

Answer each one in your head first, then open it.

Why does the outer loop need node !== null as well as stack.length > 0?

After popping the root of a subtree, the stack can be empty while that node's right subtree is still unvisited. node holds that right child, so the loop must keep running.

How many pushes happen in total for a tree of n nodes?

Exactly n. Each node is pushed once, when the walk first reaches it, and popped once.

In the trace, what is on the stack right before 6 is popped?

Only [6]. 2 and 4 were already popped and recorded, and 6 was waiting for its whole left subtree to finish.

When is the stack biggest?

On a chain leaning left, where all n nodes are pushed before the first pop. On a chain leaning right it never holds more than one node.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule at the top of the outer loop: result holds the first part of the inorder list, and what's still to visit is, in order, the subtree rooted at node, then each node on stack from top to bottom, each one followed by its right subtree. At the start, result and stack are empty and node is the root, which describes the whole tree.

The inner loop keeps the rule. Pushing node and moving to node.left says "first the left subtree, then node, then its right subtree", which is the definition of inorder. The pop keeps it too: the top node's left subtree has been fully recorded, so the top node is the next one in inorder, and after it comes its right subtree, which becomes the new node.

Each node is pushed exactly once, when node first reaches it, and popped exactly once. After 2n stack steps nothing is left to visit: node is null and stack is empty, so the loop stops, and by the rule result holds every node in inorder.

Going deeper

3 more ideas

What the stack holds

The stack always holds the nodes whose left subtree is being visited and whose own value is not recorded yet. They are exactly the calls a recursive version would have waiting on the call stack. The node on top is the closest one, so it is the next one to record.

Preorder and postorder with a stack

Preorder is simpler: push the root; then pop a node, record it, and push its right child before its left child, so the left one is popped first. For postorder, run that preorder loop but push left before right, which records node, right, left; reversing the result gives left, right, node.

Time and memory

Every node is pushed once and popped once, so the time is O(n). The stack holds at most one path from the root, so memory is O(h) for height h, the same as recursion but in normal memory, which is much larger than the call stack.

Work it by hand

Every step in a table, with why

Walk a 5-node search tree in order. 2 has only a right child and 9 has only a left child, so the stack empties in the middle while the walk is not done.

root = [6, 2, 9, null, 4, 7]

StepActionstackresultnode afterWhy
1push 6[6][]2Start at the root. 6 can't be recorded yet because its left subtree comes first, so it is pushed and node moves to 2.
2push 2[6, 2][]null2 has no left child, so node becomes null and the inner loop stops.
3pop 2[6][2]4The top of the stack, 2, has its left side finished. Record it and move into its right child 4.
4push 4[6, 4][2]nullThe outer loop runs again because node is 4. 4 has no left child.
5pop 4[6][2, 4]nullRecord 4. Its right child is null, so the next round goes straight to popping.
6pop 6[][2, 4, 6]9The inner loop doesn't run. Popping gives 6, whose left subtree is fully recorded. The stack is now empty, but node is 9, so the outer loop keeps going.
7push 9[9][2, 4, 6]7Go left from 9: push it and move to 7.
8push 7[9, 7][2, 4, 6]null7 has no left child.
9pop 7[9][2, 4, 6, 7]nullRecord 7. It has no right child.
10pop 9[][2, 4, 6, 7, 9]nullRecord 9. Now node is null and the stack is empty at the same time, so the outer loop ends.

[2, 4, 6, 7, 9], the sorted order of this search tree. Each of the 5 nodes was pushed once and popped once, 10 stack steps in all. The loop ends only when node === null and the stack is empty together.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Iterative tree traversal with a stackO(n)O(h)The tree may be very deep, or you need to stop or pause partway.
Recursive depth-first searchO(n)O(h)The depth is known to be small, as in a balanced tree, and short code matters most.
Morris traversalO(n)O(1)Memory is very tight and you may change pointers for a short time.
Parent pointersO(n)O(1)Nodes already store a parent link, like parentNode in the DOM, so you can find the next node by climbing up instead of keeping a stack.

Extra memory: O(h): the stack holds at most one path from the root. For a chain leaning left that is all n nodes. For a chain leaning right it's one node at a time, because each node is popped before its right child is pushed.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Iterative tree traversal with a stack and the other approaches, on a scale where each line up is 10 times more steps.
  • Iterative tree traversal with a stack, Recursive depth-first search, Morris traversal, Parent pointers O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Iterative tree traversal with a stack101,0001 million
Recursive depth-first search101,0001 million
Morris traversal101,0001 million
Parent pointers101,0001 million

Inputs that need care

5 tricky inputs
An empty tree: root = null
node is null and the stack is empty, so the outer loop never runs and the result is [].
A chain leaning right: 1, then 2, then 3
The stack is empty after every pop, but node holds the next right child, so the || in the outer condition keeps the loop going. With only while (stack.length > 0), the walk would stop after 1.
A chain leaning left, 50,000 nodes deep
The inner loop pushes all 50,000 nodes before the first pop. That's fine for an array, and it's exactly the input this version exists for.
Stopping at the k-th smallest value
Return as soon as result.length === k, or count instead of filling result. Nothing needs cleaning up, unlike Morris traversal, because the tree was never changed.
The tree changes during the walk
Nodes already on the stack are still popped and recorded, even if they were removed from the tree. If the tree can change, finish the walk first or copy what you need.

Variations and follow-ups

Twists interviewers add

Preorder with one stack

Push the root. Pop a node, record it, then push its right child and then its left child, so the left one comes out first. It's shorter than inorder because a node is recorded the moment it's popped.

Postorder

Run the preorder loop but push left before right, which records node, right, left. Reversing that list gives left, right, node, which is postorder. A one-stack version also exists: it remembers the last node it recorded to know whether it's coming back from the right side.

A lazy iterator

Keep node and stack as fields of an object with a next() method that runs the loop only until the next pop. Each call costs O(1) on average, which lets you merge two search trees or find a pair with a given sum without building full lists.

Generators

A function* with yield node.val in place of result.push(node.val) gives the same lazy iterator with less code, and a for...of loop can read it directly.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "without recursion", "iterator", "next() and hasNext()", "k-th smallest", or a note that the tree can be very deep.
  • Explain the stack as "the calls the recursive version would be waiting on". That sentence makes the push-left, pop, go-right pattern feel natural instead of memorized.
  • Write the outer condition with both parts, node !== null || stack.length > 0, and test it on a tree whose root has only a right child. That input catches the most common bug.
  • A usual follow-up: "build an iterator whose next() is O(1) on average and uses O(h) memory". Keep stack as a field, push the left side of the root in the constructor, and in next() pop one node and push the left side of its right child.

Where frontend code uses it

The same idea in real UI code
  • The DOM's TreeWalker (from document.createTreeWalker) moves through nodes with nextNode() one step at a time. Paused, step-by-step walks like this are what an explicit stack or parent pointers make possible.
  • Deep-cloning or comparing very deeply nested JSON (for example, a long chain of replies) with recursion can throw RangeError: Maximum call stack size exceeded; an explicit stack avoids it.
  • JavaScript generators (function*) are a common way to write a lazy tree iterator that yields one node per next() call.

Related algorithms