DSA Tracker

Visualize

Binary Tree Inorder Traversal

Left subtree, then the node, then the right subtree — the call stack holds each node until its left side is done.

time O(n)space O(h) call stack

Inorder means a node is recorded only after its entire left subtree has been, and before any of its right subtree. A node seen for the first time therefore cannot be consumed yet — it waits on the call stack while the traversal drives left, and gets its turn as the frames unwind. Watch the stack: the number of paused frames is exactly the number of nodes still owed their turn.

Details

Animated on: Given the root of a binary tree, return the inorder traversal of its nodes' values — for the tree with root 2, left subtree 7 (children 1 and 6) and right subtree 5 (right child 9).

Problem:Binary Tree Inorder TraversalEasy

Left subtree, then the node, then the right subtree — the call stack holds each node until its left side is done.

step 1 / 16

1
7
6
2
5
9

Call stack

inorder(2)

At 2. Its left child 7 must be fully handled before 2 may be recorded, so inorder(2) pauses on the stack and recurses left.

Pseudocode
1FUNCTION inorder(node):
2  IF node = null:
3    RETURN
4  inorder(node.left)
5  APPEND node.val TO out
6  inorder(node.right)
7RETURN out

← / → step · space play · Home restart

Every step in words

Show all 16 steps
  1. At 2. Its left child 7 must be fully handled before 2 may be recorded, so inorder(2) pauses on the stack and recurses left.
  2. At 7. Its left child 1 must be fully handled before 7 may be recorded, so inorder(7) pauses on the stack and recurses left.
  3. At 1. inorder(null) on its missing left child returns at once, so there is nothing to wait for — 1 can be recorded immediately.
  4. Left side of 1 is done, so APPEND 1 — it is the 1st value out. Only now, after everything to its left, may a node speak.
  5. Left side of 7 is done, so APPEND 7 — it is the 2nd value out. Only now, after everything to its left, may a node speak.
  6. 7 is recorded but not finished: its right subtree still has to come AFTER it, so recurse into 6 with inorder(7) still on the stack.
  7. At 6. inorder(null) on its missing left child returns at once, so there is nothing to wait for — 6 can be recorded immediately.
  8. Left side of 6 is done, so APPEND 6 — it is the 3rd value out. Only now, after everything to its left, may a node speak.
  9. Left side of 2 is done, so APPEND 2 — it is the 4th value out. Only now, after everything to its left, may a node speak.
  10. 2 is recorded but not finished: its right subtree still has to come AFTER it, so recurse into 5 with inorder(2) still on the stack.
  11. At 5. inorder(null) on its missing left child returns at once, so there is nothing to wait for — 5 can be recorded immediately.
  12. Left side of 5 is done, so APPEND 5 — it is the 5th value out. Only now, after everything to its left, may a node speak.
  13. 5 is recorded but not finished: its right subtree still has to come AFTER it, so recurse into 9 with inorder(5) still on the stack.
  14. At 9. inorder(null) on its missing left child returns at once, so there is nothing to wait for — 9 can be recorded immediately.
  15. Left side of 9 is done, so APPEND 9 — it is the 6th value out. Only now, after everything to its left, may a node speak.
  16. The stack is empty: every node has been recorded exactly once, giving [1, 7, 6, 2, 5, 9]. Notice the order follows the shape of the tree, not the size of the values — 7 comes before 2 because it hangs to the left.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Binary Tree Inorder Traversal in the editorAll Binary Trees problemsBack to roadmap