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.
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.
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.
Complete or perfect: what is the difference?
Perfect fills every level. Complete may leave the last level partial, filled from the left.
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.
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.
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.
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.
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.
Preorder, inorder, postorder on one tree. What changes?
Only where you record. The route is the same every time.
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.
Root → left → right. Record a node the moment you reach it. The root gets #1, and a parent always comes before its children.
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.
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).
“Return the preorder traversal.” Record the node, then left, then right.
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.
// 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; }
// Preorder: record the node, then left subtree, then right. void solve(TreeNode node, List<Integer> out) { if (node == null) return; out.add(node.val); // PRE: record before children solve(node.left, out); solve(node.right, out); } public List<Integer> preorderTraversal(TreeNode root) { List<Integer> out = new ArrayList<>(); solve(root, out); return out; }
# Preorder: record the node, then left subtree, then right. def preorderTraversal(root): out = [] def solve(node): if node is None: return out.append(node.val) # PRE: record before children solve(node.left) solve(node.right) solve(root) return out
Swapped calls, or no null check. Keep left before right. Done iteratively, push the right child first.
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.
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.
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.
“Return the inorder traversal.” Preorder with the record line moved between the two calls.
Go left, record the node, go right. On a BST this comes out sorted.
-// 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; }
-// Preorder: record the node, then left subtree, then right.+// Inorder: left subtree, then the node, then right. void solve(TreeNode node, List<Integer> out) { if (node == null) return;- out.add(node.val); // PRE: record before children solve(node.left, out);+ out.add(node.val); // IN: record between the two calls solve(node.right, out); }-public List<Integer> preorderTraversal(TreeNode root) {+public List<Integer> inorderTraversal(TreeNode root) { List<Integer> out = new ArrayList<>(); solve(root, out); return out; }
-# Preorder: record the node, then left subtree, then right.-def preorderTraversal(root):+# Inorder: left subtree, then record the node, then right.+def inorderTraversal(root): out = [] def solve(node): if node is None: return- out.append(node.val) # PRE: record before children solve(node.left)+ out.append(node.val) # IN: record between children solve(node.right) solve(root) return out
Moving the calls instead of the record line. The two calls stay where they are. Only the record line moves.
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.
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.
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.
“Return the postorder traversal.” Record after both calls, so the root comes last.
Go left, go right, then record. Any answer built from the children's answers is a postorder.
-// 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; }
-// Preorder: record the node, then left subtree, then right.+// Postorder: both subtrees first, then the node. void solve(TreeNode node, List<Integer> out) { if (node == null) return;- out.add(node.val); // PRE: record before children solve(node.left, out); solve(node.right, out);+ out.add(node.val); // POST: record after both children }-public List<Integer> preorderTraversal(TreeNode root) {+public List<Integer> postorderTraversal(TreeNode root) { List<Integer> out = new ArrayList<>(); solve(root, out); return out; }
-# Preorder: record the node, then left subtree, then right.-def preorderTraversal(root):+# Postorder: both subtrees, then record the node (root last).+def postorderTraversal(root): out = [] def solve(node): if node is None: return- out.append(node.val) # PRE: record before children solve(node.left) solve(node.right)+ out.append(node.val) # POST: record after children solve(root) return out
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).
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.
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.
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).
“Return the values level by level.” BFS with a queue, one batch per level.
Push the root. Each round, read the queue size first, pop that many nodes, collect their values and push their children.
// 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; }
// Level order: a queue, and one batch of pops per level. public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> out = new ArrayList<>(); if (root == null) return out; Queue<TreeNode> q = new ArrayDeque<>(); q.add(root); while (!q.isEmpty()) { int sz = q.size(); // exactly this level's nodes List<Integer> level = new ArrayList<>(); for (int i = 0; i < sz; i++) { TreeNode node = q.poll(); level.add(node.val); if (node.left != null) q.add(node.left); if (node.right != null) q.add(node.right); } out.add(level); } return out; }
# BFS; snapshot the level size to group nodes per level. from collections import deque def levelOrder(root): res = [] if not root: return res q = deque([root]) while q: level_size = len(q) # this level's node count level = [] for _ in range(level_size): node = q.popleft() level.append(node.val) # record the popped front if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(level) return res
Reading q.size() inside the loop. It grows as you push, so two levels merge. Read it once, before the loop.
Same preorder, your own stack: pop, record, push right, push left. Right goes in first so that left comes out first.
Why push the right child before the left?
The last push pops first. Push right, then left, and left comes out next.
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.
Push all the way left, recording nothing. Then pop, record, and step right. A pop means everything to its left is done.
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.
When does the loop stop?
Both. cur can still hold a subtree while the stack is empty, so either one alone stops early.
Run preorder with the children swapped (root, right, left) into a second stack. Empty that stack and out comes postorder.
What idea is two-stack postorder built on?
Postorder read backwards is root-right-left. That is an easy preorder; stack 2 reverses it.
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.
One stack, plus last: the node recorded most recently. If the top's right child is null or last, record it. Otherwise go right.
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.
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.
Each stack entry carries a count. 1: preorder, go left. 2: inorder, go right. 3: postorder, pop. One loop, all three orders.
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.
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.
Match the words in a question to the walk it is asking for.
copy or print a tree from the top
PREORDERO(n)read the tree from left to right
INORDERO(n)heights, sizes, deleting a tree
POSTORDERO(n)one row at a time, with a queue
LEVEL ORDER · BFSO(n)keep your own stack
ITERATIVE · STACKO(n) time · O(h) spaceread the queue's size, then pop that many
LEVEL-BATCHED BFSO(n)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.
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.
Most traversal bugs return a believable wrong order. Only the missing null check crashes.
Keep left before right. Only the record line moves. Swapped calls give a mirrored order.
if (node == nullptr) return; ends the recursion. Without it, the first null child crashes.
A stack is LIFO. Push the right child first so the left one pops next.
A skewed tree is O(n) deep and can overflow the call stack. Use your own stack instead.
Read q.size() before the inner loop. Read it inside and two levels merge into one.
Record a node when it pops, and only then. Record on push as well and every node shows up twice.
Nine traversals on one page. The right column is the cue for each.
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.
Deck 1 of 3. Decks 2 and 3 (properties, views, construction) follow.
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.