INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS
01
00/04
01 / COVER STEP 13 · BINARY TREES
INVARIANT · STEP 13 · DECK 1 OF 3
WALK THE TREE

A binary tree is a node with a value and two pointers. Everything else is a traversal: preorder, inorder, postorder (one recursion, one line moved) and level order (a queue), plus the stack versions interviewers ask for.

4Problems
2Families
12Units
12Live walks
← → ↑ ↓  or  W A S D  navigate SPACE next   DOUBLE-CLICK to advance I index   G goto problem   P predict H hide solutions   F fullscreen
INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
02 / INDEX PRESS I FROM ANYWHERE

INDEX — ALL 4 PROBLEMS

Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the problem's fixed number in this deck, not a slide position.

DFS TRAVERSALS · 03
BFS TRAVERSAL · 01
SOLVED HAS A LEETCODE LINK
INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
03 / MECHANISM UNIT 01 · TREES & THEIR TYPES

EVERY WORD HERE IS A PROPERTY OF THE PICTURE

Depth counts edges up to the root. Height counts edges down to the deepest leaf. So the root has depth 0, and a leaf has height 0.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
04 / DRILL UNIT 01 · Trees & Their Types

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Complete or perfect: what is the difference?

Perfect fills every level. Complete may leave the last level partial, filled from the left.

DRILL 02 · RECALL

One node. What is its height, and what is its depth?

Height looks down, depth looks up. The root has depth 0; a leaf has height 0.

INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
05 / MECHANISM UNIT 02 · REPRESENTING A TREE

THE SHAPE CAN BE ARITHMETIC INSTEAD OF POINTERS

Number a complete tree row by row from 0. The children of i are at 2i+1 and 2i+2, its parent at (i-1)/2. A skewed tree wastes slots: 4 nodes need indexes 0, 2, 6, 14.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
06 / DRILL UNIT 02 · Representing a Tree

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

In the array form, where is the parent of the node at index 4?

Index 1. (4-1)/2 = 1, rounded down. Check: index 1's children are 3 and 4.

DRILL 02 · RECALL

How do you check whether a node is a leaf?

Both children null. Not the same as node == null, which means there is no node at all.

INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
07 / MECHANISM UNIT 03 · THE FOUR TRAVERSALS

ONE WALK, AND A SINGLE LINE MOVES

Preorder, inorder and postorder take the same walk. Only the moment you record a node moves: before, between or after its children. Level order is different: a queue, row by row.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
08 / DRILL UNIT 03 · The Four Traversals

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Preorder, inorder, postorder on one tree. What changes?

Only where you record. The route is the same every time.

DRILL 02 · TRACE

Root 1. Its children are 2 (left) and 3 (right). Under 2 sit 4 and 5.
What is the preorder?

1, 2, 4, 5, 3. Record the node, finish the whole left side, then go right.

INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
09 / MECHANISM UNIT 04 · PREORDER

PREORDER. RECORD THE NODE, THEN ITS SUBTREES

Root → left → right. Record a node the moment you reach it. The root gets #1, and a parent always comes before its children.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
10 / DRILL UNIT 04 · Preorder

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Why does a tree function open with if (node == nullptr) return;?

null is the base case. It ends the recursion, and stops you reading a node that is not there.

DRILL 02 · TRACE

Bench tree: 1 on top, 2 and 3 below, 4 and 5 under 2, 6 and 7 under 3.
Its preorder?

1, 2, 4, 5, 3, 6, 7. Record 1, finish the left side (2, 4, 5), then the right (3, 6, 7).

INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
11 / PROBLEM #01 · DFS · EASY

Binary Tree Preorder Traversal

EASY dfs ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Return the preorder traversal.” Record the node, then left, then right.

INTUITION

If the node is null, return. Otherwise record it, go left, go right. The call stack does the rest. The helper solve fills the list out.

STEPS
  1. solve(node, out): if node is null, return
  2. out.push_back(node->val) // record BEFORE the children
  3. solve(node->left, out)
  4. solve(node->right, out)
  5. Return out from solve(root, out)
RECURSIVE O(n) → ITERATIVE (UNIT 08) O(n)EVERY NODE ONCE
↕ SCROLL
// Preorder: record the node, then left subtree, then right.
void solve(TreeNode* node, vector<int>& out) {
    if (node == nullptr) return;
    out.push_back(node->val);     // PRE: record before children
    solve(node->left, out);
    solve(node->right, out);
}
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> out;
    solve(root, out);
    return out;
}
TIMEO(n)each node visited exactly once
SPACEO(h)recursion depth = height h: about log n if balanced, n for a chain
TRAP

Swapped calls, or no null check. Keep left before right. Done iteratively, push the right child first.

INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
12 / MECHANISM UNIT 05 · INORDER

INORDER. LEFT SUBTREE, THEN NODE, THEN RIGHT

Left → root → right. The record line moved between the two calls. The leftmost node gets #1, and on a BST the values come out sorted.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
13 / DRILL UNIT 05 · Inorder

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Why does inorder on a BST come out sorted?

Left is smaller, right is larger. Left, node, right at every node reads smallest to largest.

DRILL 02 · TRACE

Same tree: 1 on top, 2 and 3 below, 4 and 5 under 2, 6 and 7 under 3.
Its inorder?

4, 2, 5, 1, 6, 3, 7. Left side, then the root, then the right side. The root lands in the middle.

INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
14 / PROBLEM #02 · DFS · EASY

Binary Tree Inorder Traversal

EASY dfs ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Return the inorder traversal.” Preorder with the record line moved between the two calls.

INTUITION

Go left, record the node, go right. On a BST this comes out sorted.

STEPS
  1. solve(node, out): if node is null, return
  2. solve(node->left, out) // whole left subtree first
  3. out.push_back(node->val) // IN: record between children
  4. solve(node->right, out)
  5. Return out from solve(root, out)
O(n) TIMEEVERY NODE ONCE
-// Preorder: record the node, then left subtree, then right.+// Inorder: left subtree, then record the node, then right. void solve(TreeNode* node, vector<int>& out) {     if (node == nullptr) return;-    out.push_back(node->val);     // PRE: record before children     solve(node->left, out);+    out.push_back(node->val);     // IN: record between children     solve(node->right, out); }-vector<int> preorderTraversal(TreeNode* root) {+vector<int> inorderTraversal(TreeNode* root) {     vector<int> out;     solve(root, out);     return out; }
TIMEO(n)each node visited once
SPACEO(h)recursion depth = height h
TRAP

Moving the calls instead of the record line. The two calls stay where they are. Only the record line moves.

INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
15 / MECHANISM UNIT 06 · POSTORDER

POSTORDER. BOTH SUBTREES FIRST, THEN THE NODE

Left → right → root. Record a node after both its children, so the root comes last. Heights, sizes and deleting a tree all need this order.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
16 / DRILL UNIT 06 · Postorder

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

A node's height, or deleting a tree. Why postorder?

The parent needs its children's answers. Height is 1 + max(left, right), so both children must finish first.

DRILL 02 · TRACE

Same tree: 1 on top, 2 and 3 below, 4 and 5 under 2, 6 and 7 under 3.
Its postorder?

4, 5, 2, 6, 7, 3, 1. Both subtrees first, so the root comes last.

INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
17 / PROBLEM #03 · DFS · EASY

Binary Tree Postorder Traversal

EASY dfs ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Return the postorder traversal.” Record after both calls, so the root comes last.

INTUITION

Go left, go right, then record. Any answer built from the children's answers is a postorder.

STEPS
  1. solve(node, out): if node is null, return
  2. solve(node->left, out)
  3. solve(node->right, out) // both subtrees first
  4. out.push_back(node->val) // POST: record after children
  5. Return out from solve(root, out)
O(n) TIMEEVERY NODE ONCE
-// Preorder: record the node, then left subtree, then right.+// Postorder: both subtrees, then record the node (root last). void solve(TreeNode* node, vector<int>& out) {     if (node == nullptr) return;-    out.push_back(node->val);     // PRE: record before children     solve(node->left, out);     solve(node->right, out);+    out.push_back(node->val);     // POST: record after children }-vector<int> preorderTraversal(TreeNode* root) {+vector<int> postorderTraversal(TreeNode* root) {     vector<int> out;     solve(root, out);     return out; }
TIMEO(n)each node visited once
SPACEO(h)recursion depth = height h
TRAP

Expecting iterative postorder to be easy. Recursively it is one moved line. Iteratively it needs two stacks or a last pointer (units 10 and 11).

INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
18 / MECHANISM UNIT 07 · LEVEL ORDER (BFS)

LEVEL ORDER, BFS, ONE LEVEL AT A TIME, WITH A QUEUE

Row by row, with a queue. Take the front, record it, add its children at the back. They wait behind the rest of their row.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
19 / DRILL UNIT 07 · Level Order (BFS)

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Level order: which node do you record, and where do its children go?

Record the front, push to the back. Take from one end, add at the other.

DRILL 02 · RECALL

DFS and BFS on the same tree. What is the real difference?

A stack dives, a queue fans out. Both are O(n) time. DFS uses O(h) space, BFS O(width).

INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
20 / PROBLEM #04 · BFS · MED

Binary Tree Level Order Traversal

MED bfs ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Return the values level by level.” BFS with a queue, one batch per level.

INTUITION

Push the root. Each round, read the queue size first, pop that many nodes, collect their values and push their children.

STEPS
  1. If root is null, return empty. Push root into queue q
  2. While q not empty: levelSize = q.size(); start a new level list
  3. Repeat levelSize times: pop front, add its val to the level, push its non-null children
  4. Append the level list to the result
  5. Return the result
O(n) TIMEEVERY NODE ONCE
↕ SCROLL
// BFS; snapshot the level size to group nodes per level.
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q; q.push(root);
    while (!q.empty()) {
        int levelSize = q.size();          // this level's node count
        vector<int> level;
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front(); q.pop();
            level.push_back(node->val);    // record the popped front
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(level);
    }
    return res;
}
TIMEO(n)each node enqueued and dequeued once
SPACEO(n)the queue holds up to one full level, O(n) for the widest level
TRAP

Reading q.size() inside the loop. It grows as you push, so two levels merge. Read it once, before the loop.

INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
21 / MECHANISM UNIT 08 · ITERATIVE PREORDER

THE RECURSION HID A STACK. THIS ONE IS VISIBLE

Same preorder, your own stack: pop, record, push right, push left. Right goes in first so that left comes out first.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
22 / DRILL UNIT 08 · Iterative Preorder

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Why push the right child before the left?

The last push pops first. Push right, then left, and left comes out next.

DRILL 02 · RECALL

Recursion is shorter. Why write it iteratively?

No call-stack overflow. A chain of 100,000 nodes can crash recursion. Your own stack has far more room.

INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
23 / MECHANISM UNIT 09 · ITERATIVE INORDER

A POP MEANS THE LEFT SUBTREE IS FINISHED

Push all the way left, recording nothing. Then pop, record, and step right. A pop means everything to its left is done.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
24 / DRILL UNIT 09 · Iterative Inorder

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

You just popped a node and recorded it. Where does cur go next?

Its right child. The left side and the node are done. Only the right side is left.

DRILL 02 · RECALL

When does the loop stop?

Both. cur can still hold a subtree while the stack is empty, so either one alone stops early.

INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
25 / MECHANISM UNIT 10 · ITERATIVE POSTORDER · 2 STACKS

BUILD IT BACKWARDS, THEN REVERSE

Run preorder with the children swapped (root, right, left) into a second stack. Empty that stack and out comes postorder.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
26 / DRILL UNIT 10 · Iterative Postorder · 2 Stacks

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

What idea is two-stack postorder built on?

Postorder read backwards is root-right-left. That is an easy preorder; stack 2 reverses it.

DRILL 02 · RECALL

You move a node from stack 1 to stack 2.
In what order do its children go onto stack 1?

Left, then right. Right ends on top and comes out first, which gives root-right-left.

INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
27 / MECHANISM UNIT 11 · ITERATIVE POSTORDER · 1 STACK

ONE STACK, IF YOU REMEMBER WHERE YOU CAME FROM

One stack, plus last: the node recorded most recently. If the top's right child is null or last, record it. Otherwise go right.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
28 / DRILL UNIT 11 · Iterative Postorder · 1 Stack

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Top of the stack: record it, or go right?

Record if its right child is null or last. Otherwise the right side is still owed, so go right.

DRILL 02 · RECALL

Why does this version need last at all?

Coming back to a node looks the same as arriving. last says the right side just finished.

INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
29 / MECHANISM UNIT 12 · ALL THREE IN ONE PASS

ONE WALK, THREE ORDERS, ONE COUNTER

Each stack entry carries a count. 1: preorder, go left. 2: inorder, go right. 3: postorder, pop. One loop, all three orders.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
30 / DRILL UNIT 12 · All Three in One Pass

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

At which count does a node get added to the inorder list?

Count 2. 1 is before the children, 2 is between them, 3 is after both.

DRILL 02 · RECALL

So what are the three DFS traversals, really?

One walk, three moments. Each node is reached three times, and each order records at one of them.

INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
31 / SIGNALS WHEN YOU SEE X, REACH FOR Y

WHICH TRAVERSAL, AND WHY

Match the words in a question to the walk it is asking for.

PARENT BEFORE ITS CHILDREN

copy or print a tree from the top

PREORDERO(n)
LEFT SIDE, THEN THE NODE

read the tree from left to right

INORDERO(n)
CHILDREN BEFORE THE PARENT

heights, sizes, deleting a tree

POSTORDERO(n)
LEVEL BY LEVEL

one row at a time, with a queue

LEVEL ORDER · BFSO(n)
NO RECURSION ALLOWED

keep your own stack

ITERATIVE · STACKO(n) time · O(h) space
ONE ANSWER PER LEVEL

read the queue's size, then pop that many

LEVEL-BATCHED BFSO(n)
INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
32 / RECALL RETRIEVAL, NOT RECOGNITION

NAME THE TRAVERSAL FROM WHAT'S ASKED

DRILL 01 · TRANSFER

You need a BST's values in sorted order. Which walk?

Inorder. Left is smaller and right is larger, so left, node, right reads smallest to largest.

DRILL 02 · RECALL

Level order, grouped per level. How do you know where a level ends?

Read the queue size first. At the start of a round the queue holds exactly one level, so pop that many.

INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
33 / TRAPS PLAUSIBLE, WRONG, AND SILENT

SIX WAYS TO BE PLAUSIBLY WRONG

Most traversal bugs return a believable wrong order. Only the missing null check crashes.

SWAPPING THE CALLS INSTEAD OF MOVING THE RECORD

Keep left before right. Only the record line moves. Swapped calls give a mirrored order.

NO null CHECK

if (node == nullptr) return; ends the recursion. Without it, the first null child crashes.

ITERATIVE PREORDER: PUSHING LEFT FIRST

A stack is LIFO. Push the right child first so the left one pops next.

TOO MUCH RECURSION DEPTH

A skewed tree is O(n) deep and can overflow the call stack. Use your own stack instead.

READING THE QUEUE SIZE TOO LATE

Read q.size() before the inner loop. Read it inside and two levels merge into one.

RECORDING A NODE TWICE

Record a node when it pops, and only then. Record on push as well and every node shows up twice.

INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
34 / CHEATSHEET REVISION SURFACE

ONE SCREEN, THE WHOLE DECK

Nine traversals on one page. The right column is the cue for each.

ALGORITHM
TIME
SPACE
REACH FOR IT WHEN
Preorder (recursive)
O(n)
O(h)
root → left → right, copy/serialize, parent before child
Inorder (recursive)
O(n)
O(h)
left → root → right. BST values come out SORTED
Postorder (recursive)
O(n)
O(h)
left → right → root, bottom-up, heights, delete, tree DP
Level order (BFS)
O(n)
O(n)
queue, front-out back-in, process by level with size-batches
Iterative preorder
O(n)
O(h)
stack; push RIGHT then LEFT so left pops first
Iterative inorder
O(n)
O(h)
push all lefts, pop+record, go right; repeat
Iterative postorder (2 stacks)
O(n)
O(n)
do root-right-left into stack 2, then reverse it
Iterative postorder (1 stack)
O(n)
O(h)
track the last node returned-from to decide direction
Pre+in+post in one pass
O(n)
O(h)
stack of (node, count 1/2/3); record at the matching count
INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
35 / CLOSE STEP 13 · DECK 1 OF 3

WALK THE TREE

A binary tree is a node with two pointers. Preorder, inorder and postorder are one recursion with the record line moved; level order is a queue. Deck 2 turns these walks into depth, diameter, views and paths.

00%
OF THIS DECK SOLVED
← ALL TOPICSSTEP 07 · RECURSIONSTEP 06 · LINKED LIST

Deck 1 of 3. Decks 2 and 3 (properties, views, construction) follow.

INVARIANT · BINARY TREES · REPRESENTATION & TRAVERSALS · DECK 1 OF 3
■ TOO SMALL TO READ
1280×720
INVARIANT · STEP 13 · DECK 1 OF 3

This one needs a laptop

Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.

Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.

YOUR SCREEN0 × 0
NEEDED1060 × 610
WHAT IS WAITING ON THE LAPTOP
WATCH IT RUN, THEN RUN IT FROM MEMORY
Your progress is saved per device, so anything you tick on the laptop will be waiting there.