Chapter 14 — Trees & Binary Trees
Chapter 14 — Trees & Binary Trees
Hey everyone! Welcome to Season 4 — Non-Linear Data Structures!
So far our data has been linear — a line of elements. Trees branch out, like a family tree or a company org chart. They're the backbone of file systems, the DOM, databases, and a huge chunk of interview questions. Don't worry — with pictures and recursion, trees are friendly.
What we will cover:
- Tree vocabulary: root, leaf, height, depth
- The binary tree node
- Traversals: Inorder, Preorder, Postorder (with pictures)
- Level-order traversal (BFS on a tree)
- Recursive vs iterative traversal
- Height, diameter, counting nodes
- Interview Questions
1. Tree Vocabulary
┌─────────────────────────────────────────────────────────────┐ │ TREE ANATOMY │ ├─────────────────────────────────────────────────────────────┤ │ │ │ (1) ← ROOT (top, no parent) │ │ / \ │ │ (2) (3) ← (3) is a child of (1) │ │ / \ \ │ │ (4) (5) (6) ← LEAVES (no children) │ │ │ │ • Root : the top node │ │ • Leaf : a node with no children │ │ • Parent/Child : direct connections │ │ • Depth of a node : edges from the root to it │ │ • Height of tree : longest root→leaf path │ │ • Subtree : any node + all its descendants │ └─────────────────────────────────────────────────────────────┘
A binary tree means each node has at most two children: left and right.
2. The Binary Tree Node
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
Because each node holds smaller subtrees, almost every tree algorithm is naturally recursive (Chapter 05 pays off here!).
3. The Three Depth-First Traversals
The only difference is when you visit the current node relative to its children:
┌─────────────────────────────────────────────────────────────┐ │ Tree: (1) │ │ / \ │ │ (2) (3) │ │ / \ │ │ (4) (5) │ ├─────────────────────────────────────────────────────────────┤ │ PREORDER (Node, Left, Right) → 1 2 4 5 3 │ │ INORDER (Left, Node, Right) → 4 2 5 1 3 │ │ POSTORDER (Left, Right, Node) → 4 5 2 3 1 │ └─────────────────────────────────────────────────────────────┘
function inorder(node, res = []) {
if (!node) return res; // base case
inorder(node.left, res); // L
res.push(node.val); // Node
inorder(node.right, res); // R
return res;
}
// Preorder: push BEFORE recursing left.
// Postorder: push AFTER recursing both.
Memory hook: the prefix (pre/in/post) tells you when the Node is visited — before, between, or after its children. For a Binary Search Tree, inorder gives sorted order (Chapter 15)!
4. Level-Order Traversal (BFS)
Visit the tree level by level, left to right. This uses a queue (remember Chapter 10!).
function levelOrder(root) {
if (!root) return [];
const res = [], queue = [root];
while (queue.length) {
const level = [];
const size = queue.length; // nodes on THIS level
for (let i = 0; i < size; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
res.push(level);
}
return res;
}
// For the tree above → [[1], [2, 3], [4, 5]]
5. Recursive vs Iterative Traversal
RECURSIVE → clean, uses the call stack (O(height) space) ITERATIVE → use an explicit Stack (DFS) or Queue (BFS) Iterative preorder with a stack: push root → pop, visit, push RIGHT then LEFT → repeat (push right first so left is processed first — LIFO!)
6. Classic Recursive Computations
// Height of a tree
function height(node) {
if (!node) return 0;
return 1 + Math.max(height(node.left), height(node.right));
}
// Count nodes
function count(node) {
if (!node) return 0;
return 1 + count(node.left) + count(node.right);
}
// Diameter (longest path between any two nodes)
function diameter(root) {
let best = 0;
function depth(node) {
if (!node) return 0;
const l = depth(node.left), r = depth(node.right);
best = Math.max(best, l + r); // path THROUGH this node
return 1 + Math.max(l, r);
}
depth(root);
return best;
}
Notice the pattern: solve for the children, then combine. That's the heart of tree recursion.
Interview Questions — Quick Fire!
Q: What's the difference between the depth of a node and the height of a tree?
"Depth is the number of edges from the root down to a specific node. Height is the number of edges on the longest path from the root to any leaf — the depth of the deepest node. A leaf has height 0; the root has depth 0."
Q: What are the three DFS traversals and how do they differ?
"Preorder visits the node before its children (Node, Left, Right), inorder visits it between them (Left, Node, Right), and postorder after them (Left, Right, Node). The position of the node in the order is the only difference. Inorder on a BST yields sorted values."
Q: How do you do a level-order traversal?
"Use a queue. Start with the root, then repeatedly dequeue a node, record it, and enqueue its children. Processing the queue's current size at each step groups nodes by level. It's BFS on a tree, O(n) time."
Q: Why are tree algorithms usually recursive?
"Because a tree is defined recursively — each node's left and right are themselves trees. So you solve a problem by solving it on the subtrees and combining the results, with the base case being a null node."
Q: What's the space complexity of recursive tree traversal?
"O(h) where h is the tree height, due to the call stack. For a balanced tree that's O(log n); for a skewed tree it degrades to O(n)."
Quick Recap
| Concept | Key Takeaway |
|---|---|
| Root/leaf/height | Core vocabulary. |
| Binary tree | ≤ 2 children per node. |
| Pre/In/Post | When you visit the node: before/between/after. |
| Level-order | BFS with a queue. |
| Recursion pattern | Solve children, combine. |
| Space | O(height) for recursion. |
What's Next?
Chapter 15: Binary Search Trees (BST) — add the ordering rule (left < node < right) and suddenly search, insert, and delete become O(log n).
Keep coding, keep grinding! See you in the next one!
Post a Comment