Trees (Basics)

Trees are everywhere — your file system, the DOM, JSON, every JS AST, every database index, every git commit history. The reason: trees model hierarchy, and almost everything we organise as humans is hierarchical. Once you can write a recursive tree function in your sleep, an enormous category of problems becomes a one-line answer.

What a Tree Actually Is

A tree is a connected, acyclic graph with one designated root. Each node has zero or more children and (except the root) exactly one parent. There is exactly one path between any two nodes — that's what "tree" means structurally.

The piece you'll work with 90% of the time is the binary tree: each node has at most a left and right child.

` 1 ← root / \ 2 3 / \ 4 5 ← leaves `

The Vocabulary You'll Use Constantly

Term	Meaning
Root	The top node (no parent)
Leaf	A node with no children
Parent / Child	Direct connection above / below
Sibling	Same parent
Depth of node	Edges from root *down to* it (root depth = 0)
Height of node	Edges on longest path *down* to a leaf (leaf height = 0)
Height of tree	Height of the root
Subtree	A node + all of its descendants
Ancestor / Descendant	Anything on the path up / in the subtree

People mix up depth and height all the time. Depth grows downward from the root; height grows upward from the leaves.

Daily Mental Model: "Solve It for One Node"

Almost every tree problem follows this template:

1. Think of \f(node)\ as "the answer for the subtree rooted at \node\". 2. Define the base case (\null\ node). 3. Recurse on \left\ and \right\, trust they return the correct answer. 4. Combine those two results with the current node's value.

Once you adopt this mindset, "max depth", "is balanced?", "diameter", "sum of paths", "invert tree", "lowest common ancestor" all collapse into ~5 lines.

Beginner Mistakes to Skip

1. Forgetting the null base case. \function depth(n) { return 1 + Math.max(depth(n.left), depth(n.right)); }\ — crashes the moment a leaf's child is read. Always start with \if (!n) return 0;\. 2. Confusing depth and height. Depth is from the *root*; height is from the *leaves*. The root has depth 0; leaves have height 0. 3. Using BFS when you need DFS (and vice versa). Path/sum/depth problems → DFS. Shortest path / level-by-level / "first occurrence at minimum depth" → BFS. 4. Iterative DFS without an explicit stack. Without it you can't simulate recursion — and you'll need it for in-order traversal. 5. Comparing trees with \===\. That just compares references. Tree equality is a recursive structural check. 6. Assuming any binary tree is balanced. Worst-case heights can be O(n). Recursion depth on a skewed tree of 100k nodes will blow the stack.

Intermediate: The Four Traversals

Three are DFS variants (different visit *position*); one is BFS.

Inorder (Left → Node → Right) — for a BST this gives sorted order.

`js function inorder(node, out = []) { if (!node) return out; inorder(node.left, out); out.push(node.val); inorder(node.right, out); return out; } `

Preorder (Node → Left → Right) — natural fit for serialisation and copying a tree (you visit a node before its children, so you can rebuild parent links easily).

Postorder (Left → Right → Node) — natural fit for deleting a tree (children freed before parent) and evaluating expression trees (operands before operator).

Level-order (BFS) — visits one level at a time, top to bottom, using a queue.

`js function levelOrder(root) { if (!root) return []; const q = [root], out = []; while (q.length) { const size = q.length, level = []; for (let i = 0; i < size; i++) { const n = q.shift(); level.push(n.val); if (n.left) q.push(n.left); if (n.right) q.push(n.right); } out.push(level); } return out; } `

The "snapshot \q.length\ at the start of each iteration" trick is the standard way to traverse one level at a time.

Intermediate: DFS vs BFS Trade-offs

Aspect	DFS	BFS
Data structure	Stack (or recursion)	Queue
Space	O(h) — height	O(w) — max width
Best for	Path sums, depths, "exists"	Shortest path, level views, "find min depth"
On balanced tree	O(log n) space	O(n / 2) ≈ O(n) space
On skewed tree	O(n) space	O(1) space	The space situation flips depending on tree shape — that's worth pausing on. A near-perfect binary tree has ~n/2 leaves on the bottom level, so BFS holds half the tree at once. DFS only holds one root-to-leaf path. Intermediate: Binary Tree Shapes You'll See in Problems	Type	Definition	Where it shows up
Full (strict)	Every node has 0 or 2 children	expression trees
Complete	All levels full *except* possibly the last, which fills left-to-right	heaps
Perfect	All internal nodes have 2 children, all leaves on the same level	textbook proofs
Balanced	For every node,	height(L) − height(R)	≤ 1	AVL, well-behaved BSTs
Degenerate (skewed)	Each node has only one child	worst case → linked list, O(n) operations

A handful of identities to know:

• Max nodes at depth \d\ = \2ᵈ\.
• Max nodes in a tree of height \h\ = \2^(h+1) − 1\.
• Min height for \n\ nodes = \⌊log₂ n⌋\.
• A tree with \n\ nodes always has \n − 1\ edges.

Advanced: Iterative Traversals (Without Recursion)

You'll be asked to do this in interviews to show you understand the call stack. Iterative inorder:

`js function inorderIter(root) { const stack = [], out = []; let node = root; while (node || stack.length) { while (node) { stack.push(node); node = node.left; } node = stack.pop(); out.push(node.val); node = node.right; } return out; } `

Iterative preorder is even simpler: push root, while stack non-empty pop, visit, push right then left. Iterative postorder is trickiest — usually done with two stacks or by reversing a "modified preorder" (root → right → left, then reverse).

Advanced: Morris Traversal — O(1) Space Inorder

The clever idea: temporarily thread the rightmost node of each left subtree to point at its in-order successor.

1. If the current node has no left child → visit it, go right. 2. Otherwise, find the rightmost node of the left subtree (the in-order predecessor): - If its \right\ is \null\ → set it to \current\ (thread it), go left. - If its \right\ is already \current\ → undo the thread, visit \current\, go right.

The threads are temporary — every modification is undone before the function returns. O(n) time, O(1) space, no stack at all. The price: it temporarily mutates the tree.

Advanced: Reconstructing Trees from Traversals

Two traversals are usually enough to uniquely rebuild a binary tree:

• Preorder + Inorder ✓ — preorder's first element is the root; find it in inorder to split into left/right; recurse.
• Postorder + Inorder ✓ — postorder's last element is the root; same split idea.
• Preorder + Postorder ✗ — only unique for full binary trees, otherwise ambiguous.

The key insight every time: inorder gives the left/right split; preorder/postorder gives the root.

Advanced: Lowest Common Ancestor (LCA) — General Binary Tree

The cleanest LCA algorithm — five lines, O(n):

`js function lca(root, p, q) { if (!root

root === p

root === q) return root; const L = lca(root.left, p, q); const R = lca(root.right, p, q); if (L && R) return root; // p and q split here → this is the LCA return L || R; // both on one side → bubble up } `

It's a perfect example of "solve for one node and trust the recursion".

Advanced: Serialisation, Diameter, and Friends

Serialise / deserialise — preorder with a null marker:

` 1 / \ → "1,2,#,#,3,4,#,#,5,#,#" 2 3 / \ 4 5 `

To deserialise, read tokens in order; if "#" → null; otherwise create node and recurse on left then right.

Diameter — longest path between any two nodes. At every node, the answer is \height(left) + height(right)\. Compute heights once with DFS while updating a running max.

Symmetric — call \isMirror(left, right)\ recursively comparing \(L.left, R.right)\ and \(L.right, R.left)\.

Invert (mirror) — recursively swap left and right at every node.

Advanced: Where Trees Live in the Real World

• DOM — every HTML element is a tree node; JS query selectors traverse it.
• AST — your TS / JS / Python source is parsed into a tree before compilation.
• File systems — directories are nodes, files are leaves.
• Decision trees / random forests — ML.
• Expression trees — \(3 + 4) * 5\ becomes a tree the compiler walks postorder.
• Heaps — implemented as complete binary trees stored in arrays.
• Tries — character-indexed trees for prefix lookup.
• B-trees / B+ trees — every database index in MySQL, PostgreSQL, MongoDB.
• Git — commit DAG (almost a tree, with merge nodes).

Practice Path

1. Write recursive \maxDepth(root)\ and \isBalanced(root)\ — both should be one short function each. 2. Implement all four traversals (in/pre/post/level) on the same tree. Verify the in-order of \[5,3,8,1,4,7,9]\ (BST) is sorted. 3. Solve Lowest Common Ancestor of a binary tree. Trace the recursion on a small example. 4. Serialise a tree to a string with preorder + "#" markers. Deserialise it back. Round-trip on a 7-node tree.