Trees
Trees are hierarchical data structures where each node has zero or more children. Binary trees (at most two children per node) and binary search trees (left < root < right) are the most common. Tree problems naturally lend themselves to recursive solutions — the key insight is that a tree problem can often be decomposed into the same problem on the left and right subtrees.
When to Use
- →You need to traverse or search hierarchical data
- →The problem involves paths from root to leaf or between nodes
- →You need to validate a BST property or find a specific node
- →You need to serialize, deserialize, or construct a tree
- →You need to compute properties like height, diameter, or balance
Approach
Most tree problems use one of two traversal strategies: DFS (depth-first search) or BFS (breadth-first search). DFS is naturally recursive — process the current node, then recurse on children. The three DFS orders are: preorder (root, left, right), inorder (left, root, right — gives sorted order for BSTs), and postorder (left, right, root — useful when you need children's results first).
BFS uses a queue to process nodes level by level. This is ideal for level-order traversal, finding the minimum depth, or any problem that requires processing nodes in distance order from the root.
For many problems, define a recursive function that returns information from subtrees. For example, to find the diameter, each recursive call returns the height of its subtree while updating a global maximum for the longest path through any node. This "return info upward while tracking global answer" pattern is extremely common.
Code Template
// DFS traversal patterns
function inorder(root, result = []) {
if (!root) return result;
inorder(root.left, result);
result.push(root.val);
inorder(root.right, result);
return result;
}
// BFS level-order traversal
function levelOrder(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length) {
const level = [];
const size = queue.length;
for (let i = 0; i < size; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
}
return result;
}
// DFS with return value (max depth / height)
function maxDepth(root) {
if (!root) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}