Fundamentals/Patterns/Tree — DFS (Recursive)26 problems· Trees

Recursive function processes a node, then recurses on left and right

When to useMax depth, validate BST, path sum, any tree property derivable from subtrees

recursive
Downhill
downhill
Balanced Binary Tree
balanced_binary_tree
Closest BST Values II
closest_bst_values_ii
Flatten Binary Tree to Linked List
flatten_binary_tree
Insert Into BST
insert_into_bst
Invert Binary Tree
invert_binary_tree
K-th Smallest Number In BST
kth_smallest_number_in_bst
Lowest Common Ancestor of a Binary Tree
lowest_common_ancestor
Lowest Common Ancestor of a Binary Search Tree
lowest_common_ancestor_on_bst
Serializing and Deserializing Binary Tree
serializing_tree
Subtree with Maximum Average
subtree_with_maximum_average
Tree DP Introduction
tree_dp_intro
Max depth of a binary tree
tree_max_depth
Valid Binary Search Tree
valid_bst
Visible Tree Node | Number of Visible Nodes
visible_tree_node
Depth First Search
dfs_intro
DFS on Trees
dfs_on_trees_intro
DFS with States
dfs_with_states
Highest Tenure
highest_tenure
Diameter Of Binary Treeeasy
diameter_of_binary_tree · no slots
Maximum Depth Of Binary Treeeasy
maximum_depth_of_binary_tree · no slots
Same Treeeasy
same_tree · no slots
Subtree Of Another Treeeasy
subtree_of_another_tree · no slots
Sum Of Left Leaveseasy
sum_of_left_leaves · no slots
Validate Binary Search Treemedium
validate_binary_search_tree · no slots
House Robber IIImedium
house_robber_iii
BASE CASE
if node === null return identity (0/null/true/etc.)
if (paths[node][0] === -1) return men > 0 ? 1 : 0;
if (node === null) return 0;
if (node === null) return;
if (node === null) return;
if (root === null) return { val, left: null, right: null };
if (root === null) return null;
if (node === null) return;
if (!root) return null;
if (root === node1 || root === node2) return root;
if (root === null) return -1;
if (!root) { res.push("x"); return; }
// (handled by n-ary loop — leaf: node.children is empty)
if (node === null) return 0;
if (root === null) return 0;
if (!root) return true;
if (!node) return 0;
if (node === null) return;
if (node === null) return -Infinity;
if (node.children.length === 0) {
res.push([...path, node.val].join('->'));
return;
}
if (!node) return [0, 0];
if (node === null) return [0, 0];
RECURSE
left = dfs(node.left); right = dfs(node.right)
for (let i = 0; i < childCount; i++) {
const portion = Math.floor(remaining / (childCount - i));
remaining -= portion;
const left = dfs(node.left);
if (left === -1) return -1;
const right = dfs(node.right);
if (right === -1) return -1;
dfs(node.left);
dfs(node.right);
dfs(node.left);
if (val < root.val) root.left = insertIntoBST(root.left, val);
else if (val > root.val) root.right = insertIntoBST(root.right, val);
const left = invertTree(root.left);
const right = invertTree(root.right);
dfs(node.left);
if (count === 0) return;
const left = lca(root.left, node1, node2);
const right = lca(root.right, node1, node2);
if (p < root.val && q < root.val) return lowestCommonAncestorBST(root.left, p, q);
if (p > root.val && q > root.val) return lowestCommonAncestorBST(root.right, p, q);
res.push(root.val);
serializeDFS(root.left, res);
serializeDFS(root.right, res);
for (const child of node.children) {
const [childSum, childCount] = dfs(child);
sum += childSum;
count += childCount;
}
const left = depth(node.left);
const right = depth(node.right);
// (inlined — no separate variables needed)
// (bounds threading — not standard left/right returns)
return dfs(root.left, minVal, root.val) && dfs(root.right, root.val, maxVal);
const left = dfs(node.left, Math.max(maxSoFar, node.val));
const right = dfs(node.right, Math.max(maxSoFar, node.val));
for (const child of node.children ?? []) {
visit(child);
}
const left = dfs(node.left);
const right = dfs(node.right);
for (const child of node.children) {
if (child) {
for (const child of (node.children ?? [])) {
const [childSum, childCount] = dfs(child);
sum += childSum;
count += childCount;
}
const left = dfs(node.left);
const right = dfs(node.right);
[COMBINE]
combine node's value with left/right results
totalCaught += probability(children[i], portion) / childCount;
}
return 1 + Math.max(left, right);
if (result.length < k) {
result.push(node.val);
} else if (Math.abs(node.val - x) < Math.abs(result[0] - x)) {
result.shift();
result.push(node.val);
} else {
return;
}
node.right = prev;
node.left = null;
prev = node;
return root;
root.left = right;
root.right = left;
return root;
count--;
if (count === 0) { result = node.val; return; }
dfs(node.right);
if (left && right) return root;
return left || right;
return root.val;
const avg = sum / count;
if (avg > bestAvg) { bestAvg = avg; bestNode = node; }
return [sum, count];
best = Math.max(best, left + right);
return 1 + Math.max(left, right);
return Math.max(dfs(root.left), dfs(root.right)) + 1;
if (!(minVal < root.val && root.val < maxVal)) return false;
const visible = node.val >= maxSoFar ? 1 : 0;
return visible + left + right;
result.push(node.val);
return Math.max(node.val, left, right);
dfs(child, path);
if (isManager) {
const avg = sum / count;
if (avg > bestAvg) { bestAvg = avg; bestNode = node; }
}
return [sum, count];
const robThis = node.val + left[1] + right[1];
const skipThis = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return [robThis, skipThis];
RETURN
return combined value to parent call