Trees and Graphs Explained

Trees and graphs model hierarchical and relational data. Trees are a subset of graphs (acyclic, connected). Every FAANG interview includes at least one tree or graph problem.

Binary Trees

A binary tree is a tree where each node has at most two children (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 Traversals

Inorder (Left, Root, Right) gives sorted order in a BST: 1, 2, 3, 4, 5, 6, 7.

graph TD
    A((4)) --> B((2))
    A --> C((6))
    B --> D((1))
    B --> E((3))
    C --> F((5))
    C --> G((7))
    
    style D fill:#D97A2B,stroke:#B86418,color:#fff
    style B fill:#FAF6EE,stroke:#E8DFC8
    style E fill:#FAF6EE,stroke:#E8DFC8
    style A fill:#FAF6EE,stroke:#E8DFC8
    style F fill:#FAF6EE,stroke:#E8DFC8
    style C fill:#FAF6EE,stroke:#E8DFC8
    style G fill:#FAF6EE,stroke:#E8DFC8

// Inorder traversal (recursive)
function inorder(root: TreeNode | null): number[] {
  if (!root) return [];
  return [...inorder(root.left), root.val, ...inorder(root.right)];
}

// Inorder traversal (iterative with 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)

A BST is a binary tree where left subtree values < root < right subtree values. This property enables O(log n) search, insertion, and deletion on average. Worst case (degenerate tree) is O(n).

Graph Representations

Adjacency List

// Most common : space efficient 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

// O(1) edge lookup but O(V²) space
const matrix = [
  [0, 1, 1, 0],
  [1, 0, 0, 1],
  [1, 0, 0, 0],
  [0, 1, 0, 0],
];

When to Use Each

• Tree: Hierarchical data (file systems, DOM, organizational charts). Binary tree problems: maximum depth, path sum, lowest common ancestor.
• Graph: Networks, relationships, state machines. Graph problems: connected components, shortest path, topological sort, cycle detection.

Common Mistakes

• Not handling null/empty tree : always check if root is null before traversal.
• Confusing BFS and DFS : BFS uses a queue (level-by-level), DFS uses a stack/recursion (depth-first).
• Forgetting visited set in graphs : without it, DFS/BFS can loop infinitely on cycles.
• Not recognizing tree problems disguised as array problems : many problems describe a tree structure implicitly (e.g., file system, HTML DOM).
• Ignoring the BST property : if the problem says "BST," use the property to prune branches.