Pattern visualizer

Binary Tree Preorder Traversal

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. 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..

Root, then left subtree, then right subtree — recursively

time O(n)space O(h)step 1 / 13

Call stack

preorder(1)

line 4

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

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap