THE TREE
A binary tree is just a node holding a value and two pointers, left and right. Nothing else is in the data structure. Everything you do to a tree after that is a traversal: a fixed order for visiting every node. This deck starts from the node itself, then teaches the four walks: preorder, inorder, postorder (one recursion, with a single line moved) and level order (a queue). Then every iterative, stack-based version an interviewer will ask you for. Each walk runs live on an SVG tree that numbers the nodes in visit order, with the call stack or queue right beside it.
This is not a list of problems. It is 12 learning units, and every one runs the same four beats. Go in order and the problems stop feeling random.
ASSUMEDA stack and a queue from unit 07 onward. LIFO and FIFO. Stacks & Queues is step 09 and not built yet.
4 PROBLEMS · EVERY ONE LINKS TO LEETCODE TO SOLVE
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the sheet's row, not your position — the deck teaches in the order that builds, so you will meet them slightly out of numerical sequence.
Trees are all traversal. The skill is picking the right one. The cards are the phrase in a problem that selects it: “parent before child”, “sorted”, “bottom-up”, “by level”. Get this reflex and deck 2 writes itself.
record a node the moment you reach it, then its subtrees
PREORDER (root → left → right)O(n)left subtree, then the node, then right, emits BST values in order
INORDER (left → root → right)O(n)both subtrees first, then the node. The node's answer needs its children's
POSTORDER (left → right → root)O(n)a queue, front-out back-in; the queue holds exactly one frontier
LEVEL ORDER · BFSO(n)replace the call stack with an explicit stack you push and pop yourself
ITERATIVE TRAVERSAL · STACKO(n) time · O(h) spaceBFS, but process the queue in size-batches. One batch is one level
LEVEL-BATCHED BFSO(n)Almost every tree problem is one O(n) traversal: visit each node once. The number to watch isn't time, it's recursion depth. O(h) space, which is O(n) on a skewed tree and can overflow the call stack.
TREE PROBLEM ⇒ ONE O(n) TRAVERSAL · MIND THE O(h) RECURSION DEPTH
Twelve units. First the tree itself (what it is, how it's stored), then the four traversals on the live SVG tree, then every iterative, stack-based version an interviewer asks for. Only four LC problems here. The value is the traversals, which deck 2 builds everything on.
A tree recursion makes two calls:go(node->left)go(node->right)
Now you add one more line, record(node). How many different places can it sit?
Three slots, so three traversals. Two calls split the function into three gaps: before the first, between the two, after the second. Drop record into each gap and you get three different visit orders, and notice the calls themselves never moved. Units 04 to 06 put a name to each position. Don't learn the names yet. You just counted the slots yourself, and the counting is the part worth having.
Level order reads the tree row by row. Why does a queue give you that, when a stack does not?
FIFO drains one level before it touches the next. Push the root, then keep popping the front and pushing that node's children to the back. First in, first out, so every node of the current level leaves before any of their children do. That is exactly level by level, left to right. A stack is LIFO, so it would dive to the bottom instead. Deep or wide is decided by nothing more than which end you take from.
A tree is a set of nodes connected with no cycles. A binary tree adds one restriction: every node gets at most two children, a left and a right. That's it. The vocabulary you'll use constantly: the root sits on top and has no parent, a leaf has no children, depth is how far a node sits below the root, and height is how far the furthest leaf sits below the node. Depth and height are measured from opposite ends. Worth getting straight now, because that mix-up is where the off-by-one bugs in deck 2 come from. The named shapes matter later, each one because some algorithm exploits it: full (every node has 0 or 2 children), complete (filled left to right), perfect (every leaf at the same depth), balanced (height stays O(log n)) and BST (ordered).
WHAT EXACTLY IS A BINARY TREE, AND WHAT ARE ITS NAMED SHAPES?
Complete and perfect. What is the actual difference?
Perfect is the strict one, complete is the practical one. Perfect means every level is filled, right to the bottom, exactly 2ʰ⁺¹ − 1 nodes for height h. Complete lets the last level be partial, but it must fill from the left with no gaps. That shape is not a technicality: it is what a binary heap is stored as, and it is why Count Complete Tree Nodes (deck 3) can be done in O(log²n) instead of O(n).
Same node. What is the difference between its height and its depth?
Height looks down, depth looks up. A node's height is the distance to the deepest leaf below it. Its depth is the distance to the root above it. So the root's height is the whole tree's height while its depth is 0, and a leaf is the other way round with height 0. Same node, two numbers, measured in opposite directions, mixing them up is the classic off-by-one in Maximum Depth and Diameter (deck 2).
Vocabulary, but each term is something you can point at rather than memorise. The one worth pausing on is depth against height: depth counts edges down from the root, height counts edges down to the furthest leaf, so a leaf has height 0 while the root has the height of the whole tree. They are measured from opposite ends, and swapping them is the most common slip in this deck.
In code, a node is a value plus two pointers, left and right, and each pointer either points at a child or is null. You hold the whole tree with a single pointer to the root, and from there you can reach every node by following left and right. A missing child is null. A leaf is just a node whose left and right are both null. The data structure ends there, everything from here on is about how you walk it.
HOW IS A TREE ACTUALLY STORED, AND WHAT IS A null CHILD?
Nearly every recursive tree function opens with if (node == nullptr) return ...;. Why?
null is the base case. A missing child is a null pointer, so the recursion bottoms out on its own the moment it steps onto one. You don't have to invent a stopping rule. The guard does two jobs at once: it stops you dereferencing null, and it declares what an empty subtree is worth (nothing to a traversal, 0 to a height, and so on). Leave it out and the very first leaf's null child crashes you.
How do you check whether a node is a leaf?
Both children null. A leaf is a real node that happens to have left and right both null. Keep that separate from node == null, which says there is no node here at all. The difference is not pedantic, root-to-leaf paths and path sum both hinge on spotting a leaf specifically, not an empty subtree.
The usual node carries two pointers and the shape lives in them. But number a complete tree in level order and the structure becomes arithmetic. The children of index i are at 2i+1 and 2i+2, the parent at (i-1)/2, and not one pointer is stored. The catch is in the word complete. A skewed tree of depth d would reserve 2d slots to hold d nodes.
Everything you do to a tree is a traversal, a fixed order for visiting every node exactly once. There are two families. DFS (depth-first) goes all the way down one subtree before it starts the next, and it comes in three flavours depending on when you record the node: preorder (before its children), inorder (between them), postorder (after both). BFS (breadth-first), also called level order, sweeps the tree row by row using a queue. DFS runs on a stack. Usually the call stack. BFS runs on a queue. Learn these four properly and the rest of the topic is just combining them.
WHAT ARE THE FOUR WAYS TO VISIT EVERY NODE?
DFS and BFS on the same tree. What is the structural difference?
A stack dives, a queue fans out. DFS commits to one path all the way down and then backtracks, so its frontier is a stack. BFS holds a whole level at a time, so its frontier is a queue. Both touch every node once, so both are O(n) in time. The memory is where they split: DFS costs O(h), the length of one path, and BFS costs O(width), which is up to O(n) at the bottom level.
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. Preorder records the node first, so 1 comes out. Then it finishes the entire left subtree before touching the right: record 2, then its left child 4, then its right child 5. Only now does it go to 3. Two of the wrong answers are real walks of this same tree, which is what makes them tempting: 4, 5, 2, 3, 1 is its postorder and 1, 2, 3, 4, 5 is its level order.
The overview for the four units that follow. All three DFS orders take the identical walk over the tree, same route, same nodes, reached in the same sequence. The only thing that changes is where the record step sits relative to the two recursive calls: before, between, or after. Level order is the odd one out, because it is not a DFS at all. It is a queue, so it reads row by row instead of branch by branch.
Preorder is root → left → right: record a node the instant you reach it, then go into its left subtree, then its right. In code that is three lines after the null check. record; go left; go right. Since the parent always comes out before its children, preorder is the natural order for copying or serializing a tree (deck 3): whoever reads your output already has the parent by the time the children arrive. The iterative version swaps the call stack for one you push and pop yourself (unit 08).
WHAT COMES OUT IF YOU RECORD THE NODE BEFORE ITS CHILDREN?
In preorder, when exactly does a node get added to the output?
Straight away, before either child. The record line sits first, right after the null check, so out goes the node, then its whole left subtree, then its whole right subtree. That is why the output always opens with the root, and why it reads as 'a node, followed by everything below it on the left, then everything below it on the right'.
The mechanism tree: 1 on top, 2 and 3 below it, 4 and 5 under 2, 6 and 7 under 3.
Write out the full preorder.
1, 2, 4, 5, 3, 6, 7. Record 1. Go left into 2 and finish it completely, 2, then 4, then 5. Only then go right into 3. 3, then 6, then 7. The other answers are all real walks of this tree, which is exactly why they look plausible: 4, 2, 5, 1, 6, 3, 7 is the inorder, 4, 5, 2, 6, 7, 3, 1 the postorder, 1, 2, 3, 4, 5, 6, 7 the level order. Press P on the mechanism slide and call each node before it lights up.
Preorder is root → left → right: you record a node the moment you reach it, before going into either subtree. The recursion is three lines. Record, go left, go right, and the call stack on the right is nothing more than the path from the root down to wherever you currently are. Watch the badges land: the root is always #1, and a subtree is numbered completely before its sibling gets started. This is the order you would copy or serialize a tree in, because the parent always comes out ahead of its children.
“Return the preorder traversal.” The canonical DFS walk. record the node, then recurse left, then right.
If the node is null, return. Otherwise record its value, then go left, then go right. The call stack does all the bookkeeping for you. The solution is nothing more. The iterative version in unit 08 does the same thing with a stack you push yourself, right child before left.
// 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
Swapping the two recursive calls, or dropping the null check. The calls must stay left then right; swapping them mirrors the traversal. For the iterative version, remember a stack is LIFO, push the right child first so the left pops next, or you'll produce a right-to-left preorder.
Inorder is left → root → right. It is the preorder recursion with one change: the record line slides down to sit between the two calls, so a node is not recorded until its entire left subtree is done. Same skeleton, completely different output. And here is the property that makes inorder matter: on a binary search tree, inorder hands you the values in sorted ascending order. No fact in this deck gets used more, in the whole BST section.
WHAT HAPPENS WHEN THE RECORD LINE MOVES BETWEEN THE TWO CALLS?
Why does inorder on a BST come out sorted?
Left-node-right, applied to left < node < right. At every node, inorder emits the smaller side, then the node, then the larger side. Apply that all the way down and the leftmost node. The smallest value in the tree. comes out first, and the rightmost comes out last. Nothing is being sorted here; the order was already in the shape. This is why the answer to validate-BST, kth-smallest and the BST iterator is always 'inorder'.
Same mechanism tree: 1 on top, 2 and 3 below, 4 and 5 under 2, 6 and 7 under 3.
What is the inorder?
4, 2, 5, 1, 6, 3, 7. Run down to the bottom left first, nothing gets recorded on the way. 4 comes out, then its parent 2, then 2's right child 5. Now the left subtree is finished, so the root 1 goes out, and the right subtree gives 6, 3, 7 the same way. Notice where the root landed: dead centre. This is the signature of inorder.
Inorder is left → root → right: a node is not recorded until its entire left subtree is done. One thing moved. The record line now sits between the two calls instead of before them, and the whole visit order changes. Watch which node gets badge #1: the leftmost leaf, not the root. On a binary search tree this order emits the values sorted, and that single fact is why inorder turns up on nearly every problem in the BST section.
“Return the inorder traversal.” The same recursion as preorder, with the record line moved between the two recursive calls.
Go left, record the node, go right. The only change from preorder is when you record, after the left subtree instead of before it. On a BST that ordering is what makes the output come 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
Reordering the recursive calls instead of moving the record line. The two solve(left)/solve(right) calls stay in place; only the record statement moved down one line versus preorder. On a BST this is your sorted-order walk, the most reused fact of the BST section.
Postorder is left → right → root: a node is recorded only after both its subtrees are finished, so the root always comes last. Same recursion again. The record line has just moved to after both calls. This children-before-parent order is the shape of every bottom-up computation. A node's height, its size, its DP answer are all built out of its children's answers, so the children have to finish first. That is not a preference, it is a dependency, and it is why half of deck 2 turns out to be a postorder wearing a different name.
WHY DOES BOTTOM-UP WORK FORCE YOU TO RECORD LAST?
Computing a node's height, or deleting a whole tree. Why is postorder the natural fit?
The parent's work needs the children's answers. Height is 1 + max(leftHeight, rightHeight). There is nothing to compute until both children have reported back. Deleting is the same shape for a different reason: free the node first and you have just orphaned two subtrees you can no longer reach. Any 'combine the children's results at the node' computation is a postorder, which is exactly what most of deck 2's DP-style problems are.
Same tree again: 1 on top, 2 and 3 below, 4 and 5 under 2, 6 and 7 under 3.
What is the postorder?
4, 5, 2, 6, 7, 3, 1. Finish the left subtree completely, 4, 5, and only then their parent 2. Then the right subtree the same way, 6, 7, then 3. The root cannot go until both are done, so 1 is last. The tell reads like this: preorder puts the root first, inorder puts it in the middle, postorder puts it last.
Postorder is left → right → root: a node is recorded only once both its subtrees are complete, so the root is always last. Badge #7 here. Same walk again, with the record line moved after both calls. This children-before-parent order is what you need whenever a node's answer is built out of its children's answers: deleting a tree, heights, sizes, any bottom-up tree DP. Half of deck 2's problems are a postorder in disguise.
“Return the postorder traversal.” Same recursion again, with the record line moved to after both recursive calls. The root comes last.
Go left, go right, then record the node. Both subtrees finish before the node does, which is exactly what any bottom-up computation needs. Heights, sizes, deleting a tree. Recursively this is trivial. The iterative versions in units 10 and 11 are the fiddliest traversals in the deck.
-// 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
Assuming iterative postorder is as easy as preorder. Recursively it's a one-line move (record after both calls). Iteratively it's the hardest of the four. Either two stacks (reverse a root-right-left walk) or one stack with a 'last visited' pointer (units 10–11). Recognise postorder whenever a node's answer depends on its children's.
Level order is breadth-first: go through the tree one level at a time, top to bottom, left to right, using a queue instead of recursion. Push the root. Then keep repeating three things. Pop the front, record it, push its non-null children to the back. Because a queue is FIFO, one whole level is drained before the next one starts. And if you read queue.size() at the top of a round, you know exactly how many nodes this level has, which lets you group nodes by level. That grouping is the trick behind zig-zag, right-side view and every 'by level' problem in deck 2.
HOW DO YOU SWEEP THE TREE LEVEL BY LEVEL WITH A QUEUE?
In the level-order loop, which node do you record, and where do its children go?
Pop the front, record that, push its children to the back. Those two ends are what produce strict level-by-level, left-to-right order. Take from one end, add at the other. Record children as you push them instead, or push to the front, and the order breaks quietly, sometimes visiting a node twice.
You have just popped node 1 and recorded it.
What is in the queue now, and who pops next?
The queue is [2, 3], and 2 pops next. Popping 1 pushed its children 2 and 3 to the back, in that order. FIFO means 2 went in first so 2 comes out first, then 3, which finishes level 1 before anything from level 2 (4, 5, 6, 7) is touched. Toggle P on the mechanism slide and you get asked exactly this.
Level order is breadth-first: top to bottom, left to right, using a queue instead of recursion. Pop the front, record it, push its children to the back. Because a queue is FIFO, everything on one level is processed before anything on the next. watch the queue hold exactly the current frontier and nothing else. Read the queue's size at the start of a round and you have one level isolated, which is what zig-zag, right-side view and almost every 'by level' problem in deck 2 are built on.
“Return the values level by level” (a list per level). 'By level' means breadth-first, a queue, batched by level size.
BFS with a queue. Push the root. Then each round: read the queue size first. That is exactly how many nodes this level has, and pop that many, collecting their values into one level's list and pushing their children for the next round. Repeat until the queue is empty.
// 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 inner loop. The size must be snapshotted before the inner loop. It grows as you push children, so reading it live merges the next level into the current one. Also push children to the back and record the front, or the left-to-right order breaks.
Iterative preorder replaces the call stack with a stack you manage yourself. Push the root. Then loop: pop a node, record it, and push its right child first, then its left. A stack is LIFO, so the left child, pushed last. is the one that pops next, and you get root → left → right with no recursion anywhere. That right-before-left push is the whole trick, and this is the easiest of the iterative traversals to get right.
HOW DO YOU DO PREORDER WITH YOUR OWN STACK INSTEAD OF RECURSION?
Why push the right child before the left?
A stack reverses whatever you give it. You want the left subtree handled first, so the left child has to be sitting on top. The last thing you push is what lands on top, so push right, then left. Do it the other way round and you get a right-to-left preorder, which looks completely reasonable in the output and is wrong.
The recursive version is shorter. So why write the iterative one at all?
You control the depth. Recursion's memory is the call stack. O(h), which becomes O(n) on a skewed tree shaped like a linked list, and that can blow the system stack. Your own stack lives on the heap, where a few hundred thousand frames is not a problem. The visit order is identical; only the machinery underneath changes. Interviewers ask for it a lot. (Morris traversal in deck 3 takes it all the way down to O(1) space.)
Every recursive traversal is already using a stack; you just could not see it. Make it explicit and preorder becomes three lines. Pop, record, push both children. The one detail that matters is the push order, right before left, because a stack reverses what you give it, so pushing right first is what makes left come off first. Watch the stack hold [3, 2] after the root: node 3 sits there untouched for five steps while the entire left subtree is dealt with. That parked node is the recursion's pending call frame.
Iterative inorder is the trickier one. You keep a curr pointer and a stack, and the loop alternates between two moves. First: while curr isn't null, push it and go left. You are running down the left spine, recording nothing. Then, when you cannot go left any further, pop a node, record it, and point curr at its right child. Push all the lefts, then pop-record-go-right. That cycle reproduces left → root → right exactly.
HOW DO YOU DO INORDER ITERATIVELY WITH A STACK AND A CURSOR?
You just popped a node and recorded it. Where does curr go next?
curr = popped->right. Think about what is already done by the time a node pops: its whole left subtree is recorded, and now the node itself is too. The only thing inorder still owes it is the right subtree. Pointing curr there sends the next iteration down that subtree's left spine, and left-root-right just keeps going.
When does the loop stop?
Both: curr null AND the stack empty. Each one means something different. A non-null curr means there is still a subtree to descend, even if the stack happens to be empty at that instant. A non-empty stack means there are ancestors still waiting to be recorded. Stop on either one alone and you exit early with half a traversal, a very common bug here.
Inorder cannot record on the way down, because a node is not due until its whole left subtree is. So the loop runs all the way down the left spine, pushing as it goes and recording nothing, then a pop is the signal that everything to the left is complete, so the node is recorded and the walk turns right. Note the shape: an inner push-left loop wrapped in an outer pop loop. So this needs both a stack and a cursor, where preorder needed only the stack.
Iterative postorder with two stacks is the easy postorder. Notice this first: postorder is left → right → root, and read backwards that is root → right → left, which is just a preorder with the children swapped. So do that mirrored preorder, pushing left then right, and drop each node onto a second stack as you go. Now pop the second stack. Out comes postorder, because popping a stack reverses it. Two stacks, and no pointer bookkeeping at all.
HOW DO TWO STACKS TURN POSTORDER INTO AN EASY MIRRORED PREORDER?
What is the one observation the two-stack postorder is built on?
reverse(postorder) = root-right-left. Write out left-right-root, read it backwards, and you get root-right-left, a mirrored preorder, which a single stack produces without any effort. So generate that easy order, push each node onto a second stack, and pop it. The reversal does the hard part for you. The price is O(n) extra space, and what you buy is zero pointer bookkeeping.
You pop a node off stack 1 and push it onto stack 2.
Now its children go back onto stack 1, in what order?
Left then right. What you want flowing into stack 2 is root-right-left, so the right child must be handled before the left, so right has to end up on top of stack 1, push left first, right second. Stack 2 then reverses the whole thing into postorder. Note this is the exact opposite of iterative preorder, where you push right then left, and for the exact same reason.
Postorder is the awkward one. A node is due only after both subtrees, so a single pop can never tell you it is finished. The trick sidesteps that entirely: run a preorder with the children swapped, which emits root-right-left, and push each result onto a second stack. Draining that stack reverses the sequence into left-right-root, which is postorder. No visited-marker, no bookkeeping. The reversal does all the work, at the cost of O(n) extra space. Watch stack 2 fill in the RESULT column, then empty in exactly the right order.
Iterative postorder with one stack is the space-tight version, and the fiddly one. You walk down like inorder, but before you can record a node you have to be sure its right subtree is finished. So keep track of the last node you recorded. When you come back up to a node and its right child is either null or exactly that last node, both subtrees are done. Record it. Otherwise you still owe it the right subtree, so descend there. One stack, O(h) space, no reversal.
HOW DO YOU DO POSTORDER WITH A SINGLE STACK AND A 'LAST VISITED' MARKER?
You are looking at the node on top of the stack.
Record it, or go right?
Right child null or already recorded ⇒ record. Otherwise go right. Postorder needs both subtrees done first. The left one is guaranteed done by the way you descended, so the only open question is the right. If the right child is null there is nothing to wait for, and if it is exactly prev then you just came back up from it. Either way the node is ready. Record it, set prev to it, pop. If neither holds, descend right. That prev check is the only thing stopping you from descending the same right subtree forever.
Why does this version need prev at all?
Because a node's second visit looks identical to its first. A node sits on the stack the whole time both its subtrees are being processed, so when you arrive back at it, the stack alone cannot tell you whether the right subtree is still pending or already finished. prev, the node you recorded most recently. Settles it: if prev is this node's right child, you are on the way back up and the node is done. Without it you would descend right forever.
Doing postorder in a single stack means solving the problem the two-stack version dodged: standing at a node, has its right subtree already been done, or not yet? The answer is one variable, last, the node recorded most recently. If a node's right child is last, you are coming back up from it and the node is finished; otherwise you still owe it a visit and descend right. That single comparison replaces the whole second stack, trading O(n) extra space for O(1). It is the fiddliest of the five and the one worth being able to rebuild from the idea rather than from memory.
All three in one pass is where the deck's claim gets proved. Push each node onto the stack carrying a count of 1, 2 or 3. On count 1: add it to preorder, bump the count to 2, go left. On count 2: add it to inorder, bump to 3, go right. On count 3: add it to postorder and pop it. Every node gets touched exactly three times, once per count, so one walk hands you all three orders together. Those three counts are the three record-points, made visible.
HOW DOES ONE STACK PASS PRODUCE PRE, IN AND POST TOGETHER?
At which count does a node get added to the inorder list?
Count 2. The three counts line up exactly with the three record-points you counted in the warmup: 1 is 'before the children' (preorder), 2 is 'between them' (inorder), 3 is 'after both' (postorder). Bumping the count and leaving the frame on the stack is simulating the recursion coming back to the node after each subtree finishes.
So what does this one pass actually tell you about the three DFS traversals?
One walk, three record-points. A single depth-first walk passes every node three times, arriving at it, coming back from the left, coming back from the right. Preorder records at the first of those moments, inorder at the second, postorder at the third. That is all they have ever been. The deck said this in unit 03; here it is running in front of you.
The punchline of the deck. Preorder, inorder and postorder differ only in when a node is recorded relative to its two descents, so give every stack frame a visit count and let one loop do all three. Count 1 emits to preorder and descends left; 2 emits to inorder and descends right; 3 emits to postorder and pops the frame. A node is touched exactly three times, so this is still O(n), and all three lists come out together. If the deck's earlier claim. That the traversals are one recursion with the record line moved, needed proof, this is it, made literal.
You need every value of a Binary Search Tree in sorted order. Which traversal, and why does it work?
Inorder. A BST's rule is left < node < right at every single node, so walking left-then-node-then-right hands you the values smallest to largest. This one fact carries a huge share of the BST section. Validate-BST, kth-smallest, BST iterator and recover-BST are all just 'do something during an inorder walk'.
You are doing level order iteratively and you need the nodes grouped per level. How do you know where one level ends?
Read the queue size at the start of each round. Right before a level begins, the queue holds exactly that level's nodes and nothing else. So pop that many times, push children as you go, and you have isolated one level. This size-batching is what zig-zag, right-side view, level averages and nearly every 'by level' problem in deck 2 are built on.
Traversal bugs are quiet: a mirrored order from swapped calls, a missing null check, left-before-right on the stack, a level-size read too late. Each returns a believable-but-wrong sequence.
For all three DFS traversals the recurse(left) and recurse(right) calls stay exactly where they are, in that order. Only the record line moves. Swap the calls and you get a mirror-image, right-to-left traversal, which quietly passes every symmetric test case and fails the rest.
if (node == nullptr) return; is the line that ends the recursion. Drop it and you dereference a null child and crash, or, in a half-written iterative version, loop forever. Every traversal opens with the null check.
Your own stack is LIFO, so to visit left first you have to push the right child first and the left second. The left lands on top and pops next. Push left first and you get a right-to-left preorder. Nothing crashes; the answer is just wrong.
Recursive traversal costs O(h) stack frames. On a skewed tree, one shaped like a linked list. That is O(n), and for large n it overflows the call stack. When depth is the risk, move to an iterative traversal with your own stack, or Morris (deck 3, O(1) space).
If you want per-level groups, read queue.size() before the inner loop and loop exactly that many times. Read size() inside the loop and it keeps growing as you push children, so two levels merge into one. Common, and it looks perfectly reasonable.
Record the node you just popped from the front, never one you are pushing. Record children as you enqueue them and the left-to-right order scrambles and nodes get visited twice.
Nine traversals, one page. The right column is the phrase that should trigger each, the night-before surface for the whole traversal toolkit.
A binary tree is a node with two pointers, and everything is a traversal: preorder, inorder, postorder (one recursion, three record-points) and level order (a queue). Every walk ran live on the SVG tree, numbering nodes in visit order. Deck 2 turns these four walks into depth, diameter, views, paths and LCA, the bulk of the tree interview.
Deck 1 of 3. Uses lectures L1-L13 (L3, Java representation, folded behind the code tabs). The iterative-traversal lectures are concept units, the four LC problems live on the recursive units, with iterative taught alongside. Decks 2-3 (properties, views, construction) to 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.