DSA Tracker

Visualize

Binary Tree Preorder Traversal

Root, then left subtree, then right subtree — recursively

time O(n)space O(h)

Preorder is the traversal where you process a node the moment you reach it, then deal with its left subtree, then its right. Because nothing is deferred, the recursion is the whole algorithm: emit, go left, go right. The call stack is what remembers, after the left subtree finishes, that the right subtree of the same node is still owed. Watch the #n badge on each node — it is the position that node takes in the output, and it is assigned on the way DOWN, never on the way back up.

Details

Animated on: Return the values of the tree [1, 2, 3, 4, 5, null, 6, null, null, 7] in preorder: each node before anything in its subtrees.

Problem:Binary Tree Preorder TraversalEasy

Root, then left subtree, then right subtree — recursively

step 1 / 13

4
2
7
5
1
#1
3
6

Call stack

preorder(1)

Enter the root, node 1. Preorder emits a node the instant we arrive, before looking at either child — that is the whole definition. out = [1].

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

← / → step · space play · Home restart

Every step in words

Show all 13 steps
  1. Enter the root, node 1. Preorder emits a node the instant we arrive, before looking at either child — that is the whole definition. out = [1].
  2. Enter left child of 1, node 2. It takes slot #2 before any of its descendants, because emitting happens on the way down. out = [1, 2].
  3. Enter left child of 2, node 4. It takes slot #3 before any of its descendants, because emitting happens on the way down. out = [1, 2, 4].
  4. 4 is a leaf: both preorder(null) calls hit the base case and return at once, so this frame pops with nothing more to do.
  5. Enter right child of 2, node 5. It takes slot #4 before any of its descendants, because emitting happens on the way down. out = [1, 2, 4, 5].
  6. Enter left child of 5, node 7. It takes slot #5 before any of its descendants, because emitting happens on the way down. out = [1, 2, 4, 5, 7].
  7. 7 is a leaf: both preorder(null) calls hit the base case and return at once, so this frame pops with nothing more to do.
  8. The whole left subtree of 1 is done (4 nodes returned). Control comes back to preorder(1), which now recurses right.
  9. Enter right child of 1, node 3. It takes slot #6 before any of its descendants, because emitting happens on the way down. out = [1, 2, 4, 5, 7, 3].
  10. 3 has no left child, so preorder(null) returns immediately and we go straight to the right subtree. Nothing is emitted for a null.
  11. Enter right child of 3, node 6. It takes slot #7 before any of its descendants, because emitting happens on the way down. out = [1, 2, 4, 5, 7, 3, 6].
  12. 6 is a leaf: both preorder(null) calls hit the base case and return at once, so this frame pops with nothing more to do.
  13. Every frame has returned. out = [1, 2, 4, 5, 7, 3, 6] — every node sits before everything in its own subtrees, and the left subtree of each node sits entirely before its right one.

Now solve it yourself

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

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