Trees are everywhere. You just don't see them. Every folder on your computer is a node in a **file system tree**. Every `

` nested inside another `

` is a node in the **DOM tree**. Every database query that runs in milliseconds instead of minutes? Thank a **B-tree** index. Every time your phone auto-suggests the next word you're typing? That's a **trie**. Every decision an AI model makes as it classifies your email as spam or not? **Decision tree**. Trees are arguably the most versatile data structure in all of computer science. Once you understand them, an enormous number of systems, algorithms, and interview problems suddenly click into place. They're the bridge between the linear world of arrays and linked lists and the more complex world of graphs, heaps, and advanced algorithms. > If arrays are a straight road, and linked lists are a one-lane highway, trees are a highway interchange: branching, hierarchical, and capable of getting you where you need to go fast. By the end of this guide, you'll: - Understand what trees are and why they matter - Know every piece of **tree terminology** (root, leaf, height, depth, and more) - Build **binary trees** from scratch in TypeScript - Master the **four fundamental traversals**: in-order, pre-order, post-order, and level-order - Implement a full **Binary Search Tree (BST)** with search, insert, delete, and validation - Understand the **Big O** complexity of every tree operation - See how trees power real-world systems from file explorers to databases - Be ready to tackle tree problems in coding interviews Let's climb in. --- ## What Is a Tree? A **tree** is a **hierarchical data structure** made up of **nodes** connected by **edges**. Unlike linear structures (arrays, linked lists, stacks, queues), trees organize data in a parent-child relationship that branches outward, just like a real tree, except we draw it upside down with the root at the top. Every tree has a few fundamental rules: 1. There is exactly **one root node** (the top of the tree, no parent) 2. Every other node has exactly **one parent** 3. There are **no cycles** — you can't follow edges and loop back to where you started 4. There is exactly **one path** between any two nodes If you break any of these rules, you don't have a tree — you have a **graph** (which is a more general structure we'll cover later). ### The Family Tree Analogy The easiest way to think about trees is the analogy right in the name: a **family tree**. - The **great-grandparent** at the top is the **root** - Each person can have **children** - Children who share the same parent are **siblings** - People with no children are **leaves** (end of the line) - The number of generations from top to bottom is the **height** ``` Great Grandparent ← root / \ Grandparent A Grandparent B ← children of root / \ | Parent A Parent B Parent C ← grandchildren of root / \ | You Sibling Cousin ← leaves (no children) ``` Every node knows its children. Every child has exactly one parent. No loops. That's a tree. ### Visualizing a Simple Tree Here's a tree holding numbers: ``` 1 ← root / | \ 2 3 4 ← children of 1 / \ | 5 6 7 ← grandchildren of 1 / \ 8 9 ← leaves ``` - **Node 1** is the root (no parent) - **Nodes 5, 6, 8, 9** are leaves (no children) - **Node 4** has one child (7) - **Node 7** has two children (8, 9) - The path from 1 to 8 is: `1 → 4 → 7 → 8` > **Key Insight**: Trees are recursive by nature. Every node in a tree is itself the root of a **subtree**. Node 4 is the root of the subtree `{4, 7, 8, 9}`. This recursive property is why so many tree algorithms use recursion — the structure itself is recursive. --- ## Tree Terminology Before we write any code, let's nail down the vocabulary. Every term here will come up in interviews, documentation, and technical discussions. Reference this tree for the definitions below: ``` 10 ← root / \ 5 15 ← internal nodes / \ / \ 3 7 12 20 ← 3, 7, 12 are internal; 20 is also internal / \ \ 1 14 25 ← leaves ``` | Term | Definition | Example from the tree above | |---|---|---| | **Root** | The topmost node with no parent | `10` | | **Parent** | A node that has one or more children | `5` is parent of `3` and `7` | | **Child** | A node directly connected below another node | `3` and `7` are children of `5` | | **Sibling** | Nodes that share the same parent | `5` and `15` are siblings | | **Leaf** | A node with no children (also called an external node) | `1`, `7`, `14`, `25` | | **Internal node** | A node that has at least one child | `10`, `5`, `15`, `3`, `12`, `20` | | **Edge** | The connection between a parent and a child | The link from `10` to `5` | | **Path** | A sequence of nodes connected by edges | `10 → 15 → 12 → 14` | | **Depth** | The number of edges from the **root** down to a node | Depth of `12` = 2 (root → 15 → 12) | | **Height** | The number of edges from a node down to the **deepest leaf** | Height of `15` = 2 (15 → 12 → 14) | | **Height of tree** | The height of the root node | Height = 3 (10 → 5 → 3 → 1) | | **Level** | All nodes at the same depth (level = depth) | Level 2: `{3, 7, 12, 20}` | | **Subtree** | A node and all its descendants | Subtree rooted at `15`: `{15, 12, 20, 14, 25}` | | **Degree** | The number of children a node has | Degree of `10` = 2; degree of `3` = 1 | > **Common confusion**: **Depth** counts **down from the root**. **Height** counts **up from the deepest leaf**. The root has depth 0 and the maximum height. A leaf has height 0 and the maximum depth. Don't mix these up — it's one of the most common mistakes in interviews. --- ## Types of Trees: A Bird's-Eye View Trees come in many flavors, each optimized for different use cases. Here's a quick map of the landscape: | Tree Type | Key Property | Common Use | |---|---|---| | **General Tree** | Each node can have any number of children | File systems, org charts | | **Binary Tree** | Each node has at most 2 children | Foundation for BSTs, heaps | | **Binary Search Tree (BST)** | Left < root < right ordering | Searching, sorting | | **AVL Tree** | Self-balancing BST (height difference ≤ 1) | Databases, lookups | | **Red-Black Tree** | Self-balancing BST (color-based rules) | `std::map` in C++, Java's TreeMap | | **Heap** | Parent is always greater (or less) than children | Priority queues, scheduling | | **Trie** | Each path from root represents a prefix | Autocomplete, spell check | | **B-Tree / B+ Tree** | Self-balancing, many children per node | Database indexes, file systems | | **Segment Tree** | Stores intervals/segments for range queries | Range sum, range min queries | In this article, we'll go deep on **binary trees** and **binary search trees** — the two you need to master first. They're the foundation for everything else in the list. Once you understand these, AVL trees, Red-Black trees, heaps, and tries are natural extensions. --- ## Binary Trees A **binary tree** is a tree where each node has **at most two children**, commonly called the **left child** and the **right child**. Binary trees are the most studied tree type because: - They're simple enough to reason about - They're the basis for BSTs, heaps, expression trees, and Huffman coding - Most tree interview questions are about binary trees - The recursive structure (each subtree is also a binary tree) makes them elegant to work with ``` A / \ B C ← A has two children / \ \ D E F ← B has two, C has one / G ← E has one (left child only) ``` ### Types of Binary Trees Not all binary trees are created equal. Understanding these subtypes matters for Big O analysis and interview questions. **Full Binary Tree** — Every node has either **0 or 2 children**. No node has just one child. ``` 1 / \ 2 3 ← Full: every node has 0 or 2 children / \ 4 5 ``` **Complete Binary Tree** — All levels are completely filled **except possibly the last**, and the last level is filled **from left to right**. ``` 1 / \ 2 3 ← Complete: last level filled left-to-right / \ / 4 5 6 ``` **Perfect Binary Tree** — All internal nodes have exactly 2 children and all leaves are at the **same level**. A perfect binary tree with height `h` has `2^(h+1) - 1` nodes. ``` 1 / \ 2 3 ← Perfect: all leaves at same level / \ / \ 4 5 6 7 ``` **Balanced Binary Tree** — For every node, the height difference between its left and right subtrees is **at most 1**. AVL trees enforce this property. ``` 1 / \ 2 3 ← Balanced: height difference ≤ 1 everywhere / \ 4 5 ``` **Degenerate (Skewed) Binary Tree** — Every internal node has only **one child**. Essentially a linked list in tree clothing. This is the **worst case** for BSTs. ``` 1 \ 2 \ 3 ← Degenerate: just a linked list \ 4 ``` > **Why this matters**: The performance of tree operations depends heavily on the tree's shape. A balanced tree gives O(log n) operations. A degenerate tree gives O(n) — no better than a linked list. This is why self-balancing trees (AVL, Red-Black) exist. --- ## Building a Binary Tree in TypeScript Let's start writing code. First, we need a **TreeNode** class — the fundamental building block. ### The TreeNode Class ```typescript class TreeNode { value: T; left: TreeNode | null; right: TreeNode | null; constructor(value: T) { this.value = value; this.left = null; this.right = null; } } ``` Simple and clean. Each node holds a value and optional pointers to a left and right child. The generic `` makes it work with any type. ### Manual Tree Construction With just the `TreeNode` class, we can build any binary tree by hand: ```typescript const root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); root.right.left = new TreeNode(6); root.right.right = new TreeNode(7); ``` This creates the following tree: ``` 1 / \ 2 3 / \ / \ 4 5 6 7 ``` ### Building from an Array (Level-Order) A common pattern is building a binary tree from an array where the elements are in level-order. This is how LeetCode represents trees: ```typescript function buildTree(values: (T | null)[]): TreeNode | null { if (values.length === 0 || values[0] === null) return null; const root = new TreeNode(values[0]); const queue: TreeNode[] = [root]; let i = 1; while (i < values.length) { const current = queue.shift()!; if (i < values.length && values[i] !== null) { current.left = new TreeNode(values[i] as T); queue.push(current.left); } i++; if (i < values.length && values[i] !== null) { current.right = new TreeNode(values[i] as T); queue.push(current.right); } i++; } return root; } const tree = buildTree([1, 2, 3, 4, 5, 6, 7]); // Builds the same tree as above ``` This helper is extremely useful for testing and interview practice where trees are given as arrays. --- ## Tree Traversals: The Big Four Traversal means **visiting every node in the tree exactly once**. The order in which you visit nodes determines what kind of traversal it is. There are four fundamental traversals, and mastering them is non-negotiable for interviews. Here's our reference tree for all traversal examples: ``` 4 / \ 2 6 / \ / \ 1 3 5 7 ``` ### 1. In-Order Traversal (Left, Root, Right) **Pattern**: Visit the left subtree, then the current node, then the right subtree. This is the most important traversal for BSTs because it visits nodes in **sorted ascending order**. ```typescript function inOrder(node: TreeNode | null, result: T[] = []): T[] { if (node === null) return result; inOrder(node.left, result); result.push(node.value); inOrder(node.right, result); return result; } const root = buildTree([4, 2, 6, 1, 3, 5, 7]); console.log(inOrder(root)); // [1, 2, 3, 4, 5, 6, 7] ← sorted! ``` **Visual walkthrough** — follow the numbered steps: ``` 4 / \ 2 6 / \ / \ 1 3 5 7 Step 1: Go left from 4 → 2 Step 2: Go left from 2 → 1 Step 3: 1 has no left → visit 1 ✓ Step 4: 1 has no right → back to 2 Step 5: Visit 2 ✓ Step 6: Go right from 2 → 3 Step 7: 3 has no left → visit 3 ✓ Step 8: 3 has no right → back to 4 Step 9: Visit 4 ✓ Step 10: Go right from 4 → 6 Step 11: Go left from 6 → 5 Step 12: 5 has no left → visit 5 ✓ Step 13: 5 has no right → back to 6 Step 14: Visit 6 ✓ Step 15: Go right from 6 → 7 Step 16: 7 has no left → visit 7 ✓ Result: [1, 2, 3, 4, 5, 6, 7] ``` > **Key Insight**: In-order traversal on a BST **always** produces sorted output. This is one of the most important properties to remember. If an interviewer asks you to validate a BST, in-order traversal is one approach. --- ### 2. Pre-Order Traversal (Root, Left, Right) **Pattern**: Visit the current node first, then the left subtree, then the right subtree. Pre-order is useful for **serializing** a tree (saving it to a string/file so you can reconstruct it later) and for creating a **copy** of the tree. ```typescript function preOrder(node: TreeNode | null, result: T[] = []): T[] { if (node === null) return result; result.push(node.value); preOrder(node.left, result); preOrder(node.right, result); return result; } console.log(preOrder(root)); // [4, 2, 1, 3, 6, 5, 7] ``` **Visual walkthrough:** ``` 4 / \ 2 6 / \ / \ 1 3 5 7 Step 1: Visit 4 ✓ Step 2: Go left → visit 2 ✓ Step 3: Go left → visit 1 ✓ Step 4: 1 has no children → back to 2 Step 5: Go right → visit 3 ✓ Step 6: 3 has no children → back to 4 Step 7: Go right → visit 6 ✓ Step 8: Go left → visit 5 ✓ Step 9: 5 has no children → back to 6 Step 10: Go right → visit 7 ✓ Result: [4, 2, 1, 3, 6, 5, 7] ``` > **Use cases**: Tree serialization/deserialization, copying a tree, generating prefix expressions, and creating a flat representation where the root always comes first. --- ### 3. Post-Order Traversal (Left, Right, Root) **Pattern**: Visit the left subtree, then the right subtree, then the current node last. Post-order is useful for **deleting** a tree (you delete children before the parent) and for **evaluating expression trees** (you need operand values before you can apply the operator). ```typescript function postOrder(node: TreeNode | null, result: T[] = []): T[] { if (node === null) return result; postOrder(node.left, result); postOrder(node.right, result); result.push(node.value); return result; } console.log(postOrder(root)); // [1, 3, 2, 5, 7, 6, 4] ``` **Visual walkthrough:** ``` 4 / \ 2 6 / \ / \ 1 3 5 7 Step 1: Go left from 4 → 2 → 1 Step 2: 1 has no children → visit 1 ✓ Step 3: Back to 2, go right → 3 Step 4: 3 has no children → visit 3 ✓ Step 5: Back to 2, both children done → visit 2 ✓ Step 6: Back to 4, go right → 6 → 5 Step 7: 5 has no children → visit 5 ✓ Step 8: Back to 6, go right → 7 Step 9: 7 has no children → visit 7 ✓ Step 10: Back to 6, both children done → visit 6 ✓ Step 11: Back to 4, both children done → visit 4 ✓ Result: [1, 3, 2, 5, 7, 6, 4] ``` > **Use cases**: Safe tree deletion (delete children before parent), evaluating postfix/expression trees, calculating directory sizes (need child sizes first), and dependency resolution. --- ### 4. Level-Order Traversal (BFS) **Pattern**: Visit all nodes level by level, from top to bottom, left to right. This is **Breadth-First Search (BFS)** applied to a tree. Unlike the three traversals above (which use recursion/stack — DFS), level-order uses a **queue**. ```typescript function levelOrder(root: TreeNode | null): T[][] { if (!root) return []; const result: T[][] = []; const queue: TreeNode[] = [root]; while (queue.length > 0) { const levelSize = queue.length; const currentLevel: T[] = []; for (let i = 0; i < levelSize; i++) { const node = queue.shift()!; currentLevel.push(node.value); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } result.push(currentLevel); } return result; } console.log(levelOrder(root)); // [[4], [2, 6], [1, 3, 5, 7]] ``` **Visual walkthrough:** ``` 4 Level 0: [4] / \ 2 6 Level 1: [2, 6] / \ / \ 1 3 5 7 Level 2: [1, 3, 5, 7] Queue progression: Start: [4] Process 4 → enqueue 2, 6 → Queue: [2, 6] Process 2 → enqueue 1, 3 → Queue: [6, 1, 3] Process 6 → enqueue 5, 7 → Queue: [1, 3, 5, 7] Process 1 → no children → Queue: [3, 5, 7] Process 3 → no children → Queue: [5, 7] Process 5 → no children → Queue: [7] Process 7 → no children → Queue: [] Done! ``` If you just need a flat list instead of grouped levels: ```typescript function levelOrderFlat(root: TreeNode | null): T[] { if (!root) return []; const result: T[] = []; const queue: TreeNode[] = [root]; while (queue.length > 0) { const node = queue.shift()!; result.push(node.value); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } return result; } console.log(levelOrderFlat(root)); // [4, 2, 6, 1, 3, 5, 7] ``` > **Use cases**: Finding minimum depth, printing tree level-by-level, zigzag traversal, connecting nodes at the same level, and any problem that asks about "levels" or "layers." --- ### Iterative Versions Using an Explicit Stack Recursive traversals are elegant, but they use the **call stack** implicitly. For very deep trees, this can cause a stack overflow. Iterative versions use an explicit stack and avoid this risk. **Iterative In-Order:** ```typescript function inOrderIterative(root: TreeNode | null): T[] { const result: T[] = []; const stack: TreeNode[] = []; let current = root; while (current || stack.length > 0) { while (current) { stack.push(current); current = current.left; } current = stack.pop()!; result.push(current.value); current = current.right; } return result; } ``` The idea: push nodes onto the stack as you go left. When you can't go left anymore, pop a node, visit it, then go right. This mimics the recursive pattern exactly. **Iterative Pre-Order:** ```typescript function preOrderIterative(root: TreeNode | null): T[] { if (!root) return []; const result: T[] = []; const stack: TreeNode[] = [root]; while (stack.length > 0) { const node = stack.pop()!; result.push(node.value); if (node.right) stack.push(node.right); if (node.left) stack.push(node.left); } return result; } ``` We push right before left because the stack is LIFO — we want the left child to be processed first. **Iterative Post-Order:** ```typescript function postOrderIterative(root: TreeNode | null): T[] { if (!root) return []; const result: T[] = []; const stack: TreeNode[] = [root]; while (stack.length > 0) { const node = stack.pop()!; result.unshift(node.value); if (node.left) stack.push(node.left); if (node.right) stack.push(node.right); } return result; } ``` The trick here: we do a modified pre-order (root → right → left) and reverse the result by using `unshift`. This produces the post-order (left → right → root) output. --- ### Traversal Summary | Traversal | Order | Data Structure | Key Use Case | |---|---|---|---| | **In-Order** | Left → Root → Right | Stack (recursion) | Sorted output on BSTs | | **Pre-Order** | Root → Left → Right | Stack (recursion) | Serialization, copying | | **Post-Order** | Left → Right → Root | Stack (recursion) | Deletion, expression eval | | **Level-Order** | Level by level | Queue | BFS, min depth, level grouping | > **Interview tip**: If the problem mentions "sorted order" — think in-order. If it mentions "levels" or "breadth" — think level-order. If it mentions "serialize" or "reconstruct" — think pre-order. If it mentions "bottom-up" or "evaluate" — think post-order. --- ## Binary Search Trees (BSTs) A **Binary Search Tree** is a binary tree with one powerful additional property: > For every node, **all values in its left subtree are less** than the node's value, and **all values in its right subtree are greater** than the node's value. This is called the **BST property** or the **ordering invariant**. ``` 8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13 ``` Check any node: - **Node 8**: Left subtree values `{1, 3, 4, 6, 7}` — all < 8. Right subtree values `{10, 13, 14}` — all > 8. ✓ - **Node 3**: Left `{1}` < 3. Right `{4, 6, 7}` > 3. ✓ - **Node 6**: Left `{4}` < 6. Right `{7}` > 6. ✓ This ordering property is what makes BSTs so powerful. Instead of scanning every node to find a value (O(n) like an array), you can **eliminate half the tree at each step**, much like binary search on a sorted array. ### Why BSTs Are Powerful Think of a BST as a **decision tree for searching**. At every node, you make one comparison and go either left or right. You never have to look at the other half. ``` Looking for 7 in the tree: 8 → 7 < 8, go left / 3 → 7 > 3, go right \ 6 → 7 > 6, go right \ 7 → found it! Only 4 comparisons for a tree with 9 nodes. ``` --- ### BST Class: Full Implementation Let's build a complete BST in TypeScript with all the core operations. ```typescript class BSTNode { value: T; left: BSTNode | null; right: BSTNode | null; constructor(value: T) { this.value = value; this.left = null; this.right = null; } } class BinarySearchTree { root: BSTNode | null; constructor() { this.root = null; } insert(value: T): void { this.root = this.insertNode(this.root, value); } private insertNode(node: BSTNode | null, value: T): BSTNode { if (node === null) { return new BSTNode(value); } if (value < node.value) { node.left = this.insertNode(node.left, value); } else if (value > node.value) { node.right = this.insertNode(node.right, value); } return node; } search(value: T): BSTNode | null { return this.searchNode(this.root, value); } private searchNode(node: BSTNode | null, value: T): BSTNode | null { if (node === null) return null; if (value === node.value) { return node; } else if (value < node.value) { return this.searchNode(node.left, value); } else { return this.searchNode(node.right, value); } } delete(value: T): void { this.root = this.deleteNode(this.root, value); } private deleteNode(node: BSTNode | null, value: T): BSTNode | null { if (node === null) return null; if (value < node.value) { node.left = this.deleteNode(node.left, value); } else if (value > node.value) { node.right = this.deleteNode(node.right, value); } else { // Case 1: Leaf node (no children) if (node.left === null && node.right === null) { return null; } // Case 2: One child if (node.left === null) return node.right; if (node.right === null) return node.left; // Case 3: Two children — find in-order successor const successor = this.findMin(node.right); node.value = successor.value; node.right = this.deleteNode(node.right, successor.value); } return node; } private findMin(node: BSTNode): BSTNode { while (node.left !== null) { node = node.left; } return node; } findMinValue(): T | null { if (!this.root) return null; return this.findMin(this.root).value; } findMaxValue(): T | null { if (!this.root) return null; let current = this.root; while (current.right !== null) { current = current.right; } return current.value; } inOrder(): T[] { const result: T[] = []; this.inOrderTraverse(this.root, result); return result; } private inOrderTraverse(node: BSTNode | null, result: T[]): void { if (node === null) return; this.inOrderTraverse(node.left, result); result.push(node.value); this.inOrderTraverse(node.right, result); } contains(value: T): boolean { return this.search(value) !== null; } } ``` --- ### Search — O(log n) Average Searching a BST is like a game of "higher or lower." At each node, compare the target value: - **Equal**: Found it! - **Less**: Go left (all smaller values are there) - **Greater**: Go right (all larger values are there) ```typescript const bst = new BinarySearchTree(); [8, 3, 10, 1, 6, 14, 4, 7, 13].forEach((v) => bst.insert(v)); console.log(bst.search(7)); // BSTNode { value: 7, left: null, right: null } console.log(bst.search(99)); // null console.log(bst.contains(6)); // true ``` **Walkthrough of searching for 4:** ``` 8 / \ 3 10 Step 1: 4 < 8 → go left / \ \ 1 6 14 Step 2: 4 > 3 → go right / \ / 4 7 13 Step 3: 4 < 6 → go left ↑ Found 4! Step 4: 4 === 4 → return node ``` Four nodes checked out of nine total. On a balanced tree, you always check at most O(log n) nodes because you halve the search space at each step. --- ### Insert — O(log n) Average Insertion follows the same path as search. You walk down the tree until you find a `null` spot where the new node belongs: ```typescript const bst = new BinarySearchTree(); bst.insert(8); bst.insert(3); bst.insert(10); bst.insert(6); bst.insert(1); bst.insert(14); console.log(bst.inOrder()); // [1, 3, 6, 8, 10, 14] ``` **Walkthrough of inserting 5:** ``` 8 / \ 3 10 / \ \ 1 6 14 Insert 5: 8 → 5 < 8, go left 3 → 5 > 3, go right 6 → 5 < 6, go left null → insert 5 here! Result: 8 / \ 3 10 / \ \ 1 6 14 / 5 ← new node ``` The new node is always inserted as a **leaf**. This is elegant because it never disrupts existing relationships. --- ### Delete — The Three Cases Deletion is the most complex BST operation because removing a node might break the tree structure. There are three cases: **Case 1: Deleting a leaf node (no children)** Simply remove it. No re-linking needed. ``` Delete 1: After: 8 8 / \ / \ 3 10 3 10 / \ \ \ \ 1 6 14 6 14 ``` **Case 2: Deleting a node with one child** Replace the node with its only child. ``` Delete 10: After: 8 8 / \ / \ 3 10 3 14 / \ \ / \ 1 6 14 1 6 ``` **Case 3: Deleting a node with two children** This is the tricky one. You can't just remove the node — you need to find a replacement that maintains the BST property. The strategy: replace the node's value with its **in-order successor** (the smallest value in its right subtree), then delete the successor from the right subtree. Why the in-order successor? Because it's the **smallest value that's still larger than the deleted node**, so it slots in perfectly without violating the BST property. ``` Delete 3: 8 / \ 3 10 Find in-order successor of 3: / \ \ → go right to 6 1 6 14 → go left as far as possible → 4 / \ / → successor is 4 4 7 13 Step 1: Replace 3's value with 4 Step 2: Delete 4 from the right subtree (it's a leaf → Case 1) Result: 8 / \ 4 10 / \ \ 1 6 14 \ / 7 13 ``` ```typescript bst.delete(3); console.log(bst.inOrder()); // [1, 4, 6, 7, 8, 10, 13, 14] ``` > **Alternative**: Instead of the in-order successor, you could use the **in-order predecessor** (the largest value in the left subtree). Both approaches are valid. Most implementations use the successor by convention. --- ### Validate BST — The Min/Max Range Approach A common interview question: given a binary tree, determine if it's a valid BST. The naive approach — checking only that `left < root < right` for each node — is **wrong**. It misses cases where a deeper node violates the global ordering: ``` 5 / \ 1 6 / \ 3 7 ← 3 is less than 5, violating the BST property! (everything in 5's right subtree must be > 5) ``` Node 6's left child is 3, which satisfies `3 < 6`, but it violates the global constraint that everything in the right subtree of 5 must be greater than 5. The correct approach: pass a **valid range** `(min, max)` down to each node. Each node must fall within the range set by its ancestors. ```typescript function isValidBST( node: BSTNode | null, min: number = -Infinity, max: number = Infinity ): boolean { if (node === null) return true; if (node.value <= min || node.value >= max) { return false; } return ( isValidBST(node.left, min, node.value) && isValidBST(node.right, node.value, max) ); } ``` **How the ranges propagate:** ``` 8 (min=-∞, max=+∞) / \ 3 10 (-∞,8) (8,+∞) / \ \ 1 6 14 (-∞,3) (3,8) (10,+∞) ``` Each recursive call narrows the valid range. If any node falls outside its range, the tree is not a valid BST. ```typescript const validTree = new BinarySearchTree(); [8, 3, 10, 1, 6, 14].forEach((v) => validTree.insert(v)); console.log(isValidBST(validTree.root)); // true const invalidRoot = new BSTNode(5); invalidRoot.left = new BSTNode(1); invalidRoot.right = new BSTNode(6); invalidRoot.right.left = new BSTNode(3); invalidRoot.right.right = new BSTNode(7); console.log(isValidBST(invalidRoot)); // false (3 is in right subtree of 5) ``` --- ### BST Big O: Average vs Worst Case | Operation | Average Case | Worst Case (Degenerate) | |---|---|---| | Search | **O(log n)** | O(n) | | Insert | **O(log n)** | O(n) | | Delete | **O(log n)** | O(n) | | Find Min/Max | **O(log n)** | O(n) | | In-Order Traversal | O(n) | O(n) | | Space (recursive) | O(log n) | O(n) | The average case assumes a **roughly balanced tree**. The worst case occurs when elements are inserted in sorted order, creating a degenerate tree: ``` Insert: 1, 2, 3, 4, 5 1 \ 2 \ 3 ← This is basically a linked list. \ Every operation is O(n). 4 \ 5 ``` > **This is exactly why self-balancing trees exist.** AVL trees and Red-Black trees automatically restructure themselves after insertions and deletions to guarantee O(log n) worst-case performance. We'll cover those in a future deep-dive article. --- ## Common Tree Operations Beyond traversals and BST operations, there are several utility functions that come up constantly. ### Find Height / Depth The **height** of a tree is the number of edges on the longest path from the root to a leaf. ```typescript function treeHeight(node: TreeNode | null): number { if (node === null) return -1; const leftHeight = treeHeight(node.left); const rightHeight = treeHeight(node.right); return Math.max(leftHeight, rightHeight) + 1; } const root = buildTree([1, 2, 3, 4, 5, null, null]); console.log(treeHeight(root)); // 2 ``` ``` 1 height = 2 / \ 2 3 height of left subtree = 1, right = 0 / \ 4 5 height = 0 (leaves) ``` We return `-1` for `null` so that a single node (leaf) has height `0`, which is the standard convention. **Time**: O(n) — we visit every node once **Space**: O(h) — recursive call stack, where h is the height --- ### Count Nodes ```typescript function countNodes(node: TreeNode | null): number { if (node === null) return 0; return 1 + countNodes(node.left) + countNodes(node.right); } console.log(countNodes(root)); // 5 ``` Beautifully simple recursion: a tree's node count is 1 (for itself) plus the count of its left subtree plus the count of its right subtree. The base case is `null` → 0. **Time**: O(n) **Space**: O(h) --- ### Check If Balanced A binary tree is **balanced** if, for every node, the height difference between its left and right subtrees is at most 1. ```typescript function isBalanced(node: TreeNode | null): boolean { return checkHeight(node) !== -1; } function checkHeight(node: TreeNode | null): number { if (node === null) return 0; const leftHeight = checkHeight(node.left); if (leftHeight === -1) return -1; const rightHeight = checkHeight(node.right); if (rightHeight === -1) return -1; if (Math.abs(leftHeight - rightHeight) > 1) return -1; return Math.max(leftHeight, rightHeight) + 1; } ``` We use `-1` as a sentinel value to signal "not balanced." The moment we find an imbalanced subtree, we propagate `-1` upward and short-circuit the rest of the computation. ```typescript const balanced = buildTree([1, 2, 3, 4, 5, 6, 7]); console.log(isBalanced(balanced)); // true const unbalanced = new TreeNode(1); unbalanced.left = new TreeNode(2); unbalanced.left.left = new TreeNode(3); unbalanced.left.left.left = new TreeNode(4); console.log(isBalanced(unbalanced)); // false ``` **Time**: O(n) — each node visited at most once **Space**: O(h) — recursive call stack --- ### Find Lowest Common Ancestor (LCA) The **Lowest Common Ancestor** of two nodes is the deepest node that is an ancestor of both. This is a classic interview question. For a **general binary tree** (not necessarily a BST): ```typescript function lowestCommonAncestor( root: TreeNode | null, p: T, q: T ): TreeNode | null { if (root === null) return null; if (root.value === p || root.value === q) return root; const left = lowestCommonAncestor(root.left, p, q); const right = lowestCommonAncestor(root.right, p, q); if (left && right) return root; return left ?? right; } ``` The logic: if `p` is in one subtree and `q` is in the other, the current node is the LCA. If both are in the same subtree, the LCA is deeper in that subtree. ``` 3 / \ 5 1 / \ / \ 6 2 0 8 LCA(5, 1) = 3 (5 is left, 1 is right → 3 is LCA) LCA(5, 6) = 5 (6 is under 5 → 5 is LCA) LCA(6, 2) = 5 (both under 5 → 5 is LCA) ``` For a **BST**, the solution is even simpler — use the ordering property: ```typescript function lcaBST( root: BSTNode | null, p: T, q: T ): BSTNode | null { if (root === null) return null; if (p < root.value && q < root.value) { return lcaBST(root.left, p, q); } if (p > root.value && q > root.value) { return lcaBST(root.right, p, q); } return root; } ``` If both values are less than the current node, the LCA must be in the left subtree. If both are greater, it's in the right subtree. Otherwise, the current node is the LCA (they diverge here). **Time**: O(h) for BST, O(n) for general binary tree **Space**: O(h) --- ## Real-World Applications Trees aren't abstract concepts that live only in textbooks. They're the backbone of systems you use every day. ### 1. File Systems (Directory Tree) Every operating system organizes files in a tree structure. The root directory (`/` on Unix, `C:\` on Windows) is the root node, folders are internal nodes, and files are leaves. ``` / ├── home/ │ ├── user/ │ │ ├── documents/ │ │ │ ├── resume.pdf │ │ │ └── notes.txt │ │ └── photos/ │ │ └── vacation.jpg │ └── admin/ │ └── config.yml └── etc/ └── nginx.conf ``` Commands like `ls -R` (recursive listing) perform a **pre-order traversal**. `du` (disk usage) performs a **post-order traversal** — it calculates child sizes before the parent. ### 2. The DOM (Document Object Model) Every web page is a tree. The `` element is the root, and every nested element is a child node. ``` document └── html ├── head │ ├── title │ └── meta └── body ├── header │ └── nav ├── main │ ├── article │ └── aside └── footer ``` When the browser renders a page, it parses HTML into a DOM tree, then walks that tree to calculate layout and paint pixels. JavaScript's `querySelector`, `appendChild`, and `removeChild` are all tree operations. ### 3. Database Indexes (B-Trees / B+ Trees) How does a database find a row in a table with millions of entries in milliseconds? **B-tree indexes**. A B-tree is a self-balancing tree where each node can hold multiple keys and have multiple children. This structure minimizes disk reads by keeping the tree shallow and wide. A B-tree with millions of entries might only be 3-4 levels deep, meaning any lookup requires at most 3-4 disk reads. ### 4. Autocomplete and Spell Check (Tries) A **trie** (prefix tree) stores strings character by character. Each path from root to a node represents a prefix. This makes prefix-based lookups incredibly fast — O(k) where k is the length of the word, regardless of how many words are in the trie. ``` root / | \ a b c / | p a / \ | p e t | l | e → "apple" ``` ### 5. Priority Queues (Heaps) A **heap** is a complete binary tree where the parent is always greater than (max-heap) or less than (min-heap) its children. Heaps power priority queues, which are used in: - Task scheduling (OS process scheduling) - Dijkstra's shortest path algorithm - Huffman coding (data compression) - Median finding in streaming data ### 6. Decision Trees (AI / Machine Learning) Decision trees are one of the most interpretable ML models. Each internal node represents a "question" about a feature, each branch is an answer, and each leaf is a prediction. ``` Is it raining? / \ Yes No / \ Bring umbrella Is it cold? / \ Yes No / \ Wear jacket T-shirt weather ``` Random Forests and Gradient Boosted Trees (used in XGBoost, LightGBM) are ensembles of decision trees and dominate competitive ML. ### 7. Expression Parsing Compilers convert mathematical expressions into **expression trees** (also called abstract syntax trees — ASTs). The leaves are operands and the internal nodes are operators. ``` Expression: (3 + 4) * 2 * / \ + 2 / \ 3 4 ``` A **post-order traversal** of this tree evaluates the expression bottom-up: `3, 4, +, 2, *` → `3 + 4 = 7`, then `7 * 2 = 14`. --- ## Trees vs Other Data Structures When should you use a tree instead of something simpler? Here's a comparison to help you decide: | Feature | Array | Linked List | Hash Map | BST (Balanced) | |---|---|---|---|---| | **Search** | O(n)* | O(n) | **O(1)** avg | O(log n) | | **Insert** | O(n) | O(1)† | **O(1)** avg | O(log n) | | **Delete** | O(n) | O(1)† | **O(1)** avg | O(log n) | | **Find min/max** | O(n) | O(n) | O(n) | **O(log n)** | | **Range queries** | O(n) | O(n) | O(n) | **O(log n + k)** | | **Ordered iteration** | O(n log n)‡ | O(n log n)‡ | O(n log n)‡ | **O(n)** | | **Memory** | Low | Medium | Medium-High | Medium | *\* O(log n) for sorted arrays with binary search, but insert/delete become O(n).* *† O(1) if you have a reference to the node; O(n) to find it first.* *‡ Requires sorting first.* **Choose trees when you need:** - **Sorted data with efficient insert/delete** — Hash maps give O(1) lookup but can't iterate in order or do range queries - **Range queries** — "Find all values between 10 and 50" - **Hierarchical data** — File systems, org charts, DOM - **Ordered operations** — Find min, max, successor, predecessor - **Balanced performance** — O(log n) for everything, no worst-case O(n) surprise like hash collisions --- ## Common Pitfalls Even experienced developers stumble on these. Learn them now so you don't debug them later. ### 1. Confusing Depth vs Height **Depth** goes **down** from the root. **Height** goes **up** from the deepest leaf. ``` A depth 0, height 2 / \ B C depth 1, height 1 (B), height 0 (C) / \ D E depth 2, height 0 ``` - Node A: depth = 0, height = 2 - Node B: depth = 1, height = 1 - Node D: depth = 2, height = 0 - The **tree's height** = the root's height = 2 > **Memory aid**: **D**epth = **D**own from root. **H**eight = **H**ow tall from bottom. ### 2. Assuming a BST Is Always Balanced A BST is only balanced if you insert values in a reasonable order. Inserting sorted values creates a degenerate tree: ```typescript const bst = new BinarySearchTree(); [1, 2, 3, 4, 5].forEach((v) => bst.insert(v)); // Creates a linked list, not a balanced tree! // Every operation is now O(n), not O(log n) ``` If you need guaranteed O(log n), use a self-balancing tree (AVL or Red-Black) or insert values in a randomized order. ### 3. Forgetting Null Checks in Recursive Traversals The most common cause of runtime errors in tree code: ```typescript // ❌ BAD: crashes if node is null function height(node: TreeNode): number { return Math.max(height(node.left), height(node.right)) + 1; } // ✅ GOOD: handle the base case function height(node: TreeNode | null): number { if (node === null) return -1; return Math.max(height(node.left), height(node.right)) + 1; } ``` Every recursive tree function needs a `null` base case. No exceptions. ### 4. Mixing Up Traversal Orders It's easy to confuse which traversal does what. A quick way to remember: - **In**-order: Root is **in** the middle (Left, **Root**, Right) - **Pre**-order: Root is **pre**fixed / first (***Root***, Left, Right) - **Post**-order: Root is **post**poned / last (Left, Right, ***Root***) ### 5. Validating BST with Only Local Checks ```typescript // ❌ WRONG: only checks immediate children function isBST(node: BSTNode | null): boolean { if (!node) return true; if (node.left && node.left.value >= node.value) return false; if (node.right && node.right.value <= node.value) return false; return isBST(node.left) && isBST(node.right); } // This incorrectly returns true for: // 5 // / \ // 1 6 // / \ // 3 7 ← 3 < 5, but it's in 5's right subtree! ``` Always use the **min/max range approach** we covered earlier to validate BSTs correctly. --- ## Cheat Sheet Keep this handy for interviews and quick reference. ### Traversal Orders at a Glance ``` 1 / \ 2 3 / \ 4 5 In-Order (L, Root, R): [4, 2, 5, 1, 3] Pre-Order (Root, L, R): [1, 2, 4, 5, 3] Post-Order (L, R, Root): [4, 5, 2, 3, 1] Level-Order (BFS): [1, 2, 3, 4, 5] ``` ### BST Operations ``` ┌──────────────────────────────────────────────────────┐ │ BINARY SEARCH TREE │ ├──────────────┬─────────────┬─────────────────────────┤ │ Operation │ Avg / Worst │ Notes │ ├──────────────┼─────────────┼─────────────────────────┤ │ Search │ O(log n)/O(n)│ Binary search path │ │ Insert │ O(log n)/O(n)│ Always inserts leaf │ │ Delete │ O(log n)/O(n)│ 3 cases, use successor│ │ Min / Max │ O(log n)/O(n)│ Leftmost / rightmost │ │ Validate │ O(n) / O(n) │ Must check every node │ │ Traversal │ O(n) / O(n) │ Visit all nodes │ └──────────────┴─────────────┴─────────────────────────┘ Worst case = degenerate (skewed) tree Avg case = roughly balanced tree ``` ### Common Tree Operations ``` ┌─────────────────────────────────────────────────┐ │ COMMON TREE OPERATIONS │ ├────────────────┬──────────┬─────────────────────┤ │ Operation │ Big O │ Approach │ ├────────────────┼──────────┼─────────────────────┤ │ Find height │ O(n) │ Recursive max+1 │ │ Count nodes │ O(n) │ Recursive 1+L+R │ │ Is balanced? │ O(n) │ Check height diff │ │ LCA (BST) │ O(h) │ Use BST ordering │ │ LCA (general) │ O(n) │ Recursive split │ │ Invert tree │ O(n) │ Swap left & right │ └────────────────┴──────────┴─────────────────────┘ ``` ### When to Use Trees ``` Need hierarchical data? → General tree Need sorted data + fast ops? → BST (balanced) Need guaranteed O(log n)? → AVL or Red-Black tree Need a priority queue? → Heap Need prefix-based lookups? → Trie Need fast range queries on disk? → B-tree / B+ tree Need to evaluate expressions? → Expression tree ``` ### The Tree Mental Model ``` ┌─────────────────────────────────────────────────────┐ │ TREES │ │ │ │ Structure: Hierarchical, nodes + edges, no cycles │ │ Strength: O(log n) search/insert/delete (balanced)│ │ Weakness: O(n) worst case if unbalanced │ │ Memory: 2 pointers per node (binary) │ │ │ │ Best for: Sorted data, hierarchy, range queries, │ │ ordered traversal, search problems │ │ Avoid for: Simple lookups (use hash map), │ │ flat sequential data (use array) │ └─────────────────────────────────────────────────────┘ ``` --- ## Wrapping Up Trees are one of those data structures that, once you truly understand them, unlock a massive portion of computer science. They're the foundation for databases, compilers, AI, networking, file systems, and more. And in interviews, tree problems are among the most frequently tested. Here's what we covered: - **What trees are**: Hierarchical, acyclic structures with a root node, parents, children, and leaves. They're recursive by nature — every subtree is itself a tree. - **Tree terminology**: Root, parent, child, sibling, leaf, depth, height, level, subtree, degree — the vocabulary you need for interviews and technical discussions. - **Binary trees**: Each node has at most two children. Types include full, complete, perfect, balanced, and degenerate. - **The Big Four traversals**: In-order (sorted BST output), pre-order (serialization), post-order (bottom-up evaluation), and level-order (BFS). Both recursive and iterative implementations. - **Binary Search Trees**: The sorted binary tree with O(log n) average-case search, insert, and delete. We built a complete BST class with all operations including the tricky three-case deletion. - **BST validation**: The min/max range approach that catches global ordering violations. - **Common operations**: Height, node count, balance checking, and lowest common ancestor. - **Real-world applications**: File systems, DOM, database indexes, autocomplete, priority queues, decision trees, and expression parsing. The key takeaway? Trees are **everywhere**, and the patterns you've learned here (recursive thinking, traversal strategies, the BST property) will apply again and again as you tackle more advanced data structures and algorithms. > **Remember**: A tree is only as good as its balance. An unbalanced BST is just a linked list with extra steps. Understanding *when* a tree degrades and *how* to prevent it is what separates junior developers from senior ones. --- ## What's Next? You've built a rock-solid foundation. Now it's time to go deeper and put these concepts to work. In the upcoming **“Trees and Graphs Deep Dive”** article, we'll explore: - **AVL trees** — Self-balancing BSTs with rotations - **Heaps** — Priority queues built on complete binary trees - **Tries** — Prefix trees for string operations - **DFS and BFS** on trees and graphs — the algorithmic patterns that power everything from Google Maps to social network analysis And in the **“Trees Made Simple”** problem-solving guide, we'll tackle the most common LeetCode tree problems step by step: - Maximum Depth of Binary Tree (LeetCode 104) - Invert Binary Tree (LeetCode 226) - Validate Binary Search Tree (LeetCode 98) - Lowest Common Ancestor (LeetCode 236) - Binary Tree Level Order Traversal (LeetCode 102) - Serialize and Deserialize Binary Tree (LeetCode 297) - And many more... Each problem will build on the traversal patterns and BST operations you learned here. The foundation is set — now let's sharpen it. Happy coding!

Trees 101: The Ultimate Beginner's Guide