Binary Tree Inorder Traversal

Easy#94in-order

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

94 Binary Tree Inorder TraversalWalkthrough · 1×

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

nonenonenonenonenonenonenone629743out—stacktop on the right—
not reached yeton the stack, waits for its left subtreecurin out, #n is its placenone: an empty child

out = []: nothing is visited yet

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

← → step · space play/pause

Why it works

  1. A node goes on the stack on the way down and comes off only when everything left of it is done: the stack waits exactly like the calls of the recursive walk.
  2. After a node is added, cur moves to its right subtree, so the order is always left subtree, node, right subtree.
  3. Every node is pushed and popped once, so the loop ends when cur is none and nothing is waiting.

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 one path from the root down.

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.