Binary Trees and the Three Depth-First Traversals
How a hierarchical structure differs from every linear one you've covered so far, and the three classic ways to visit every node in a specific, meaningful order.
What you'll learn
- Build a binary tree from individual nodes with left/right children
- Implement inorder, preorder, and postorder traversal, recursively
- Correctly handle the empty-tree and single-node edge cases in every traversal
Prerequisites
Explanation
A binary tree is a hierarchical structure where each node holds a value and up to two children, conventionally called left and right — the first genuinely non-linear structure in this course, since a node doesn't have one "next," it can branch into two independent subtrees. { value: 8, left: { value: 3, left: null, right: null }, right: { value: 10, left: null, right: null } } is a three-node tree with 8 at the root.
Traversal means visiting every node exactly once, in some defined order — and unlike a linear structure's single obvious order, a tree has several genuinely useful ones. Preorder (root, then left subtree, then right subtree) visits a node before its children — useful for copying a tree, since you need a node's own data before you can build its children. Inorder (left subtree, then root, then right subtree) visits a node between its children — for a specific kind of tree (a binary search tree, covered next lesson), this produces values in sorted order, which is the main reason inorder traversal matters as much as it does. Postorder (left subtree, then right subtree, then root) visits a node after both its children — useful whenever you need to process children before their parent, such as computing each node's size from its children's sizes, or safely deleting a tree from the leaves inward.
All three are naturally, elegantly expressed with recursion: each traversal function's base case is "if the node is null, do nothing" (this is exactly what makes an empty subtree — and by extension, an empty tree, and a leaf node's null children — handle themselves correctly with zero special-casing), and its recursive case just calls itself on left and right in the order that traversal defines, visiting the current node's own value at the appropriate point relative to those two calls. Getting the position of that one line — "visit this node's value" — relative to the two recursive calls is the entire difference between preorder, inorder, and postorder; the recursive structure itself is otherwise identical across all three.
Example
The same tree, traversed three ways -- notice how the ONLY difference between the three functions is where 'visit the node' happens relative to the two recursive calls.
function makeNode(value, left = null, right = null) {
return { value, left, right };
}
// 8
// / \
// 3 10
const tree = makeNode(8, makeNode(3), makeNode(10));
function preorder(node, result = []) {
if (node === null) return result; // base case: empty subtree does nothing
result.push(node.value); // visit BEFORE children
preorder(node.left, result);
preorder(node.right, result);
return result;
}
function inorder(node, result = []) {
if (node === null) return result;
inorder(node.left, result);
result.push(node.value); // visit BETWEEN children
inorder(node.right, result);
return result;
}
function postorder(node, result = []) {
if (node === null) return result;
postorder(node.left, result);
postorder(node.right, result);
result.push(node.value); // visit AFTER children
return result;
}
console.log(preorder(tree)); // [8, 3, 10]
console.log(inorder(tree)); // [3, 8, 10] -- sorted, because this happens to be a BST
console.log(postorder(tree)); // [3, 10, 8]Try it yourself
Add a left child (value 1) to the node holding 3, then re-run inorder and see where 1 lands.
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Guided exercise
Guided exercise
Write treeHeight(node) that returns a tree's height (the number of edges on the longest path from the node to a leaf; an empty tree has height -1, a single node has height 0), using postorder-style recursion (compute children's heights first, then combine).
Checks: empty tree has height -1 · single node has height 0 · an unbalanced chain reports the correct, longer height · a balanced tree reports the correct, shorter height
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Independent exercise
Independent exercise
Write countNodes(node) (total number of nodes, 0 for an empty tree) and isSameTree(a, b) (true if both trees have identical structure AND identical values at every position -- not just the same values in some order). Test against several shapes including empty trees, single nodes, and structurally different trees with the same values.
Checks: counts an empty tree as 0 nodes · counts a multi-node tree correctly · two empty trees are considered the same · a real tree and an empty tree are never the same · identical values in different structural positions are NOT the same tree · identical structure and values ARE the same tree
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Common mistakes
- Forgetting the null base case in a recursive tree function -- without it, recursion never terminates and either crashes with a stack overflow or throws on node.left of a null node.
- Confusing preorder and postorder when a specific order matters (e.g. needing children processed before their parent) -- the position of 'visit this node' relative to the two recursive calls is the entire difference, and getting it backwards silently produces a differently-ordered, wrong result rather than an error.
- Comparing two trees by collecting all values into a Set/array and comparing THAT, instead of comparing structure -- this misses cases where the same values appear in a different arrangement, which is a structurally different tree.
Knowledge check
Takeaway
A tree's branching structure means there's no single natural traversal order — preorder, inorder, and postorder each visit a node at a different point relative to its children, and all three are naturally expressed as recursion whose only real difference is where the 'visit' line sits.
Summary
A binary tree node has up to two children (left, right). Preorder visits root-left-right, inorder visits left-root-right (sorted order for a BST), postorder visits left-right-root. All three are recursive with a null base case, which correctly and automatically handles both empty trees and leaf nodes.
References
Your notes
Notes save automatically.
Finished this lesson?
Mark it complete to track your progress and schedule a future review.
AI tutor
The optional AI tutor isn't enabled in this deployment. All lessons, exercises, quizzes, and search work fully without it.