Trees and Graphs Deep Dive
Explore binary trees, BSTs, AVL trees, graph representations, and traversal algorithms.
What you'll learn
- Binary trees, BSTs, and balanced variants (AVL, red-black)
- Graph representations: adjacency list vs matrix
- DFS and BFS traversal patterns
- Tree and graph applications
Concept
Trees and Graphs Deep Dive
Trees are hierarchical structures with a root and branches; graphs generalize trees to allow cycles and multiple connections. Both are foundational for modeling relationships.
Binary Trees and BSTs
A binary tree has at most two children per node. A binary search tree (BST) maintains the invariant: left subtree values < node < right subtree values. This gives O(log n) search/insert/delete when balanced, but degrades to O(n) when unbalanced.
Self-Balancing Trees
AVL trees rebalance after each insert/delete by performing rotations, guaranteeing height O(log n). Red-black trees use a weaker balance condition but allow faster inserts. Both guarantee O(log n) operations.
Graph Representations
Adjacency list: for each vertex, store a list of neighbors. O(V + E) space, efficient for sparse graphs. Adjacency matrix: a V*V boolean matrix. O(V^2) space, O(1) edge lookup, efficient for dense graphs.
Traversals
DFS (depth-first): go deep before going wide. Uses a stack (or recursion). Good for connectivity, cycle detection, topological sort. BFS (breadth-first): visit all neighbors before going deeper. Uses a queue. Good for shortest path in unweighted graphs, level-order traversal.
For trees, the three DFS variants - preorder, inorder, postorder - serve different purposes. Inorder on a BST yields sorted output.
Example
class TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; } }
class BST {
constructor() { this.root = null; }
insert(val) {
const node = new TreeNode(val);
if (!this.root) { this.root = node; return; }
let curr = this.root;
while (true) {
if (val < curr.val) { if (!curr.left) { curr.left = node; return; } curr = curr.left; }
else { if (!curr.right) { curr.right = node; return; } curr = curr.right; }
}
}
inorder() { const r = []; const w = (n) => { if (!n) return; w(n.left); r.push(n.val); w(n.right); }; w(this.root); return r; }
}
function bfs(graph, start) {
const visited = new Set([start]); const queue = [start]; const order = [];
while (queue.length) { const v = queue.shift(); order.push(v); for (const u of graph[v] || []) { if (!visited.has(u)) { visited.add(u); queue.push(u); } } }
return order;
}
const bst = new BST();
[5, 3, 7, 1, 4, 6, 8].forEach(v => bst.insert(v));
console.log('Inorder (sorted):', bst.inorder());
console.log('BFS from 1:', bfs({1:[2,3],2:[4],3:[4,5],4:[],5:[]}, 1));
The BST keeps left < node < right, so inorder traversal yields sorted values. BFS uses a queue to visit all neighbors at the current level before descending.
Try it
- JSON Formatter
JSON is a tree structure - formatting it is a tree traversal.
Common mistakes
The mistake
Inserting sorted data into an unbalanced BST.
The fix
Sorted insertion creates a degenerate (linked-list-like) tree with O(n) operations. Use a self-balancing tree.
The mistake
Using BFS for weighted shortest path.
The fix
BFS finds shortest path in unweighted graphs only. For weighted graphs, use Dijkstra or Bellman-Ford.
Look up unfamiliar terms
A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.
Build real projects
Apply what you learned by building guided projects with starter code and solutions.
Decode error messages
Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.