Binary treesCore idea
A binary tree is a tree where every node has at most two children, called left and right.
class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val: number) {
this.val = val;
this.left = null;
this.right = null;
}
}Tree traversalsHow it works
A traversal is the order you visit the nodes. The four you need:
| Traversal | Order | Use case | On the tree above |
|---|---|---|---|
| Inorder | Left → Root → Right | Sorted order in a BST | 1, 2, 3, 4, 5, 6, 7 |
| Preorder | Root → Left → Right | Copying or serialising a tree | 4, 2, 1, 3, 6, 5, 7 |
| Postorder | Left → Right → Root | Deleting a tree, evaluating expressions | 1, 3, 2, 5, 7, 6, 4 |
| Level-order | Level by level (BFS) | Minimum depth, level averages | 4, 2, 6, 1, 3, 5, 7 |
// Recursive
function inorder(root: TreeNode | null): number[] {
if (!root) return [];
return [...inorder(root.left), root.val, ...inorder(root.right)];
}
// Iterative, with an explicit stack
function inorderIterative(root: TreeNode | null): number[] {
const result: number[] = [];
const stack: TreeNode[] = [];
let current = root;
while (current || stack.length) {
while (current) {
stack.push(current);
current = current.left;
}
current = stack.pop()!;
result.push(current.val);
current = current.right;
}
return result;
}Binary search tree (BST)Core idea
In a BST, every value in a node's left subtree is smaller than the node, and every value in its right subtree is bigger. That lets you skip half the tree at each step: search, insert and delete are O(log n) on average.
Graph representationsCompare
A graph is a set of nodes (vertices) joined by edges. There are two standard ways to store one.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","actorBkg":"#e7f5ff","actorBorder":"#1e1e1e","noteBkgColor":"#fff9db","noteBorderColor":"#1e1e1e"}}}%%
graph LR
N0((0)) --- N1((1))
N0 --- N2((2))
N1 --- N3((3))
class N0 orange
class N1,N2,N3 blue
classDef orange fill:#ffd8a8,stroke:#1e1e1e,color:#1e1e1e
classDef blue fill:#a5d8ff,stroke:#1e1e1e,color:#1e1e1e
classDef green fill:#b2f2bb,stroke:#1e1e1e,color:#1e1e1e
classDef red fill:#ffc9c9,stroke:#1e1e1e,color:#1e1e1e
classDef violet fill:#d0bfff,stroke:#1e1e1e,color:#1e1e1e
classDef yellow fill:#ffec99,stroke:#1e1e1e,color:#1e1e1e
classDef grey fill:#e9ecef,stroke:#1e1e1e,color:#1e1e1eAdjacency list
Each node keeps a list of its neighbours. This is the most common choice and uses little space for sparse graphs.
const graph: Map<number, number[]> = new Map();
graph.set(0, [1, 2]);
graph.set(1, [0, 3]);
graph.set(2, [0]);
graph.set(3, [1]);Adjacency matrix
A V × V grid where cell [i][j] is 1 if there is an edge. Checking one edge is O(1), but it always costs O(V²) space.
| Adjacency list | Adjacency matrix | |
|---|---|---|
| Space | O(V + E) | O(V²) |
| Is there an edge u–v? | O(degree of u) | O(1) |
| List all neighbours | O(degree) | O(V) |
| Best for | Sparse graphs (most problems) | Dense graphs, quick edge checks |
When to use eachWhen to use
Treehierarchy
File systems, the DOM, org charts. Typical problems: maximum depth, path sum, lowest common ancestor.
Graphrelationships
Networks, dependencies, state machines. Typical problems: connected components, shortest path, topological sort, cycle detection.
Common mistakesPitfalls
In the interviewIn the interview
Most tree problems fall apart into “what does one node do with its children's answers?” Saying that framing out loud helps you and the interviewer.
Frequently asked questionsFAQ
What is the difference between a tree and a graph?
A tree is a connected, acyclic graph, so a tree is a special case of a graph. A graph allows cycles and disconnected components, and it can have any number of neighbors per node. A tree has exactly one path between any two nodes, always has a root, and has n nodes with n minus 1 edges. If your problem has cycles or several unconnected pieces, model it as a graph.
Why does inorder traversal of a BST return sorted values?
A binary search tree guarantees that every value in a node left subtree is smaller than the node, and every value in the right subtree is larger. Inorder traversal visits left subtree, then root, then right subtree, so it emits all smaller values, then the node, then all larger values, in ascending order. The same property is what makes search, insert, and delete average O(log n) on a balanced tree.
When should you use an adjacency list instead of an adjacency matrix?
Use an adjacency list for sparse graphs, which is the common case in interviews. It stores only existing edges, so space is O(V plus E) and iterating neighbors is proportional to the actual degree. An adjacency matrix uses O(V squared) space but gives O(1) edge lookup and constant-time neighbor checks, which helps with dense graphs or many connectivity queries.
Now explain trees and graphs to me out loud
I'll give you interview problems and ask follow-ups, like a real interviewer.