DFS, BFS, height, diameter, and path problems on binary trees.
A binary tree has nodes with at most two children. Most tree problems use DFS (preorder/inorder/postorder recursion) or BFS (level order with a queue). The key mindset is: define what your recursive function returns, trust it for subtrees, and combine results at the current node.
DFS/BFS O(n)
O(h) recursion stack, O(n) for BFS queue
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
Use this as the core mindset for every tree DFS problem
Define precisely what your function returns for a node, trust that it returns the correct answer for any subtree, then combine the left and right results at the current node. Never try to manually trace deep recursion; instead focus on the base case (null node) and the recurrence.
Problem Maximum Depth of Binary Tree. The depth of a node is 1 plus the max depth of its two subtrees. The base case: null returns 0.
// Trust recursion — Maximum Depth of Binary Tree
function maxDepth(root) {
if (!root) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}Use this when you need to process a node before its children, such as when constructing a path, serializing a tree, or copying the structure
Preorder visits root, then recursively visits left and right.
Problem Path Sum II. At each node, add the value to the current path and recurse into children; pop after each recursive call to backtrack.
// Preorder DFS — Path Sum II (root-to-leaf paths)
function pathSum(root, target) {
const result = [];
function dfs(node, remaining, path) {
if (!node) return;
path.push(node.val);
if (!node.left && !node.right && remaining === node.val)
result.push([...path]);
dfs(node.left, remaining - node.val, path);
dfs(node.right, remaining - node.val, path);
path.pop();
}
dfs(root, target, []);
return result;
}Use this when the sorted order of values matters, since inorder traversal of a BST yields values in ascending order
It is also useful for in-place processing where you need to see smaller nodes first.
Problem Kth Smallest Element in a BST. Use inorder traversal and decrement a counter; return the value when the counter hits zero.
// Inorder DFS — Kth Smallest Element in a BST
function kthSmallest(root, k) {
let count = 0, result = null;
function inorder(node) {
if (!node || result !== null) return;
inorder(node.left);
if (++count === k) { result = node.val; return; }
inorder(node.right);
}
inorder(root);
return result;
}Use this when you need information from both children before you can process the current node, such as computing height, diameter, or checking balance.
Problem Diameter of Binary Tree. Compute the height of the left and right subtrees in postorder; the diameter at this node is their sum; update the global max.
// Postorder DFS — Diameter of Binary Tree
function diameterOfBinaryTree(root) {
let maxDiam = 0;
function height(node) {
if (!node) return 0;
const l = height(node.left), r = height(node.right);
maxDiam = Math.max(maxDiam, l + r);
return 1 + Math.max(l, r);
}
height(root);
return maxDiam;
}Use this when the optimal answer may span from the left subtree through the root to the right subtree and therefore cannot be passed up the call stack in a single return value
Keep an external variable that you update inside the recursive function while returning the best single-branch value upward.
Problem Binary Tree Maximum Path Sum. At each node, the cross-root path is node.val + max(left, 0) + max(right, 0); update the global max, but return only node.val + max(left, right, 0) to the parent.
// Global variable — Binary Tree Maximum Path Sum
function maxPathSum(root) {
let best = -Infinity;
function dfs(node) {
if (!node) return 0;
const l = Math.max(dfs(node.left), 0);
const r = Math.max(dfs(node.right), 0);
best = Math.max(best, node.val + l + r);
return node.val + Math.max(l, r);
}
dfs(root);
return best;
}Use this when you are given preorder (or postorder) and inorder arrays and must rebuild the tree
The first element of preorder is always the root; find its index in the inorder array to split left and right subtrees. Recurse with correctly sized subarrays.
Problem Construct Binary Tree from Preorder and Inorder Traversal. Root is preorder[0]; inorder index idx splits the array into left (size idx) and right subtrees.
// Construct tree — Build from Preorder and Inorder Traversal
function buildTree(preorder, inorder) {
if (!preorder.length) return null;
const rootVal = preorder[0];
const idx = inorder.indexOf(rootVal);
const root = new TreeNode(rootVal);
root.left = buildTree(preorder.slice(1, idx + 1), inorder.slice(0, idx));
root.right = buildTree(preorder.slice(idx + 1), inorder.slice(idx + 1));
return root;
}