Module P-4 — Tree Traversal: Inorder, Preorder, Postorder, and Level-Order
What this module covers: A tree is the first branching structure in this course — where a linked list's nodes each point to exactly one "next," a tree's nodes can point to multiple children. This module covers the four standard ways to visit every node in a binary tree, why each ordering exists for a specific reason (not just as textbook variety), and how they're implemented both recursively (Module P-1) and iteratively (Module F-6's stack, Module F-7's queue).
The Binary Tree Node
typescript
A binary tree node has at most two children, conventionally called left and right. This is a direct generalization of the linked list from Module P-2 — instead of one next pointer, there are two, and that single change is what turns a straight line into a branching structure with genuine depth.
Depth-First Traversals: Three Orders, Three Purposes
Three of the four traversal patterns visit a node and its two subtrees in a different order relative to each other — and that ordering isn't arbitrary, each one has a specific job.
Inorder (Left → Root → Right) — visits the left subtree, then the current node, then the right subtree:
typescript
Applied to a binary search tree (Module P-5, where every left subtree holds smaller values and every right subtree holds larger ones), inorder traversal visits every value in ascending sorted order automatically — no sorting step required. This is the reason inorder traversal exists as a named pattern: it's the direct way to read a BST's contents back out in order.
Preorder (Root → Left → Right) — visits the current node before either subtree:
typescript
Because the root is recorded before its children, preorder is the natural order for copying or serializing a tree's structure — if you write out preorder values and later rebuild the tree by reading them back in the same order, you can reconstruct the exact same shape, since every node's value is written down before its children's values are.
Postorder (Left → Right → Root) — visits both subtrees before the current node:
typescript
Because both children are fully processed before the parent, postorder is the natural order for deletion and bottom-up computation — you can't safely delete a node (or compute something that depends on both children, like subtree height) until you've already finished with everything beneath it. Deleting root-first in a tree you still need to walk is asking for trouble; postorder guarantees children are always handled first.
Level-Order: Breadth-First, Using a Queue
The fourth pattern doesn't recurse into depth at all — it visits the tree layer by layer, all nodes at depth 0, then all nodes at depth 1, and so on. This is exactly Module F-7's queue, applied to a tree instead of a flat sequence:
typescript
Enqueuing a node's children right after dequeuing it, and processing strictly in FIFO order, guarantees every node at depth d is dequeued before any node at depth d + 1 — because every depth-d node was enqueued (by its depth-(d-1) parent) before any depth-(d+1) node could be. Snapshotting queue.length at the start of each outer iteration (levelSize) is what lets the code know exactly where one layer ends and the next begins, without needing to track depth explicitly on each node.
Iterative Traversal: Trading Recursion for an Explicit Stack
Every depth-first traversal above is recursive, leaning on the call stack from Module P-1. Each one can also be written iteratively, using an explicit stack (Module F-6) to hold the same "what to visit next" information the call stack was managing implicitly:
typescript
Pushing right before left is deliberate: since a stack pops the most recently pushed item first, pushing right first guarantees left comes out on top — preserving the same Root → Left → Right order as the recursive version. This is the concrete answer to "what is recursion actually costing me" from Module P-1: the recursive version's call stack is doing exactly this bookkeeping, just implicitly, one frame per pending node, instead of one explicit array entry per pending node.
Where This Shows Up in Your Stack
React's reconciliation and rendering walks the component tree in a depth-first order conceptually similar to preorder — process a component, then its children — which Module P-16's capstone covers directly, connecting this module's traversal patterns to how the Virtual DOM's diffing algorithm actually works.
The DOM itself: element.children, recursively walked, is exactly this module's tree structure and preorder-style traversal — "process this node, then each child" is the shape of most DOM-walking code (finding all elements matching a selector, building a table of contents from headings, and similar tasks).
JSON serialization of nested structures is preorder traversal in practice — writing out a parent's data before recursing into its children's data is precisely what lets a JSON.stringify-style serializer reconstruct the same nested shape when parsed back.
Next.js's file-based routing organizes routes as a tree of nested folders (app/blog/[slug]/page.tsx), and resolving a URL to the right route/layout combination involves walking that tree from the root down — level-order-adjacent reasoning shows up here too, when a framework needs to resolve all matching layouts at each level of nesting before moving deeper.
Subtree height/size calculations (used directly in Module P-5 to reason about whether a binary search tree is balanced) are a canonical postorder computation — you cannot know a node's height until you know both children's heights first.
Summary
A binary tree node has up to two children (left, right) — a direct generalization of the linked list's single next pointer into a branching structure.
Inorder (L, Root, R) yields sorted order on a binary search tree — the reason it exists as a named pattern.
Preorder (Root, L, R) is the natural order for copying/serializing a tree's structure, since a node's data is recorded before its children's.
Postorder (L, R, Root) is the natural order for deletion and bottom-up computation, since both children are fully processed before the parent.
Level-order is breadth-first, built directly on Module F-7's queue — enqueue children right after dequeuing a node, and FIFO order guarantees each depth is fully processed before the next begins.
Every recursive depth-first traversal has an iterative equivalent using an explicit stack (Module F-6) — the stack holds exactly what the call stack (Module P-1) was already managing implicitly, one frame per pending node.
The next module, Binary Search Trees: Insert, Search, Delete, and Validation, gives the tree structure introduced here an ordering invariant — and shows exactly why inorder traversal producing sorted output isn't a coincidence.
Knowledge Check
Why does inorder traversal (Left → Root → Right) visit every node of a binary search tree in ascending sorted order, while preorder and postorder do not?
In levelOrder, what specific purpose does capturing levelSize = queue.length at the start of each outer while iteration serve?
In preorderIterative, why does the code push node.right onto the stack before pushing node.left, rather than the other way around?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
functioninorder<T>(node: TreeNode<T>|null,visit:(value:T)=>void):void{if(node ===null)return;// base case (Module P-1)inorder(node.left, visit);visit(node.value);inorder(node.right, visit);}inorder(root, v =>console.log(v));// 1, 2, 3, 4, 5, 6, 7 — sorted order, for a BST
functionlevelOrder<T>(root: TreeNode<T>|null):T[][]{if(root ===null)return[];const result:T[][]=[];const queue: TreeNode<T>[]=[root];// Module F-7 — FIFOwhile(queue.length >0){const levelSize = queue.length;// exactly the number of nodes at the current depthconst level:T[]=[];for(let i =0; i < levelSize; i++){const node = queue.shift()!;// dequeue — Module F-7 (a real Queue class avoids the O(n) shift cost in production code) level.push(node.value);if(node.left) queue.push(node.left);if(node.right) queue.push(node.right);} result.push(level);}return result;}levelOrder(root);// [[4], [2, 6], [1, 3, 5, 7]]
functionpreorderIterative<T>(root: TreeNode<T>|null):T[]{if(root ===null)return[];const result:T[]=[];const stack: TreeNode<T>[]=[root];// Module F-6while(stack.length >0){const node = stack.pop()!; result.push(node.value);// Push right before left, so left is popped and processed first (LIFO)if(node.right) stack.push(node.right);if(node.left) stack.push(node.left);}return result;}