Binary Tree Preorder Traversal

Easy#144pre-order

You get the root of a binary tree. Return its values in pre-order: the node first, then its left subtree, then its right subtree. Our tree: 5 with children 8 and 1; 8 has only a left child, 3; 1 has children 6 and 2 — the answer is [5, 8, 3, 1, 6, 2].

144 Binary Tree Preorder TraversalWalkthrough · 1×

Example: the pre-order of a binary tree, with a stack of our own instead of recursion. Each node has val, left and right.

nonenonenonenonenonenonenone581362out—stacktop on the right—
not reached yeton the stacknodein out, #n is its placenone: an empty child

out = []: nothing is visited yet

01/40
restart · back · play · step
Speed
1function preorderTraversal(root):
2 out = []
3 if root is none:
4 return out
5 stack = [root]
6 while stack is not empty:
7 node = stack.pop()
8 out.add(node.val)
9 if node.right is not none:
10 stack.push(node.right)
11 if node.left is not none:
12 stack.push(node.left)
13 return out
state
node
–
stack
–
out
[]
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A node is added the moment it comes off the stack, before any node under it has even been popped.
  2. The stack gives back the last thing put on it, so pushing right before left makes the whole left subtree come out before the right child.
  3. Every node is pushed once, the root at the start and the rest by their parent, and popped once, so the loop ends after n pops.

Complexity

Time O(n): every node is pushed and popped once. Memory O(h), where h is the height of the tree: the stack holds the right children waiting along one path.

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.