Binary Tree DFS Patterns
Recursive depth-first traversal for path problems, ancestor queries, and structural transformations. Most binary tree hard problems reduce to one of six canonical DFS shapes.
The Pattern
Binary tree DFS problems follow one of two return-value shapes. In the pass-down shape, you carry state from parent to child (current path, running sum, depth). In the return-up shape, you compute something at each subtree and combine results from both children at the current node (height, diameter, path sum through root). Recognising which shape applies immediately suggests the function signature.
A third class — subtree queries — applies the same DFS recursion but uses a helper that returns a value used by the outer recursive call. The "lowest common ancestor" problem is the canonical example.
Path Sum I — Does a Root-to-Leaf Path Exist?
Classic pass-down: subtract the current node's value from the target at each step. A leaf is reached when both children are None; the path is valid if the remaining target equals zero.
#[derive(Debug)]
struct TreeNode { val: i32, left: Option<Box<TreeNode>>, right: Option<Box<TreeNode>> }
fn has_path_sum(node: &Option<Box<TreeNode>>, target: i32) -> bool {
match node {
None => false,
Some(n) => {
let rem = target - n.val;
if n.left.is_none() && n.right.is_none() { return rem == 0; }
has_path_sum(&n.left, rem) || has_path_sum(&n.right, rem)
}
}
}
fn build(vals: &[Option<i32>]) -> Option<Box<TreeNode>> {
if vals.is_empty() { return None; }
fn helper(vals: &[Option<i32>], i: usize) -> Option<Box<TreeNode>> {
if i >= vals.len() { return None; }
vals[i].map(|v| Box::new(TreeNode {
val: v,
left: helper(vals, 2*i+1),
right: helper(vals, 2*i+2),
}))
}
helper(vals, 0)
}
fn main() {
// 5
// / \
// 4 8
// / / \
// 11 13 4
// /\ \
// 7 2 1
let tree = build(&[Some(5),Some(4),Some(8),Some(11),None,Some(13),Some(4),Some(7),Some(2),None,None,None,None,None,Some(1)]);
println!("{}", has_path_sum(&tree, 22)); // true (5→4→11→2)
println!("{}", has_path_sum(&tree, 26)); // true (5→8→13)
println!("{}", has_path_sum(&tree, 18)); // false
}Path Sum II — All Root-to-Leaf Paths That Sum to Target
Same pass-down shape, but collect paths instead of returning a bool. Push before recursing, pop after — standard backtracking.
fn path_sum(node: &Option<Box<TreeNode>>, target: i32, path: &mut Vec<i32>, results: &mut Vec<Vec<i32>>) {
if let Some(n) = node {
path.push(n.val);
let rem = target - n.val;
if n.left.is_none() && n.right.is_none() && rem == 0 {
results.push(path.clone());
}
path_sum(&n.left, rem, path, results);
path_sum(&n.right, rem, path, results);
path.pop();
}
}
fn main() {
let tree = build(&[Some(5),Some(4),Some(8),Some(11),None,Some(13),Some(4),Some(7),Some(2),None,None,Some(5),Some(1)]);
let mut results = Vec::new();
path_sum(&tree, 22, &mut Vec::new(), &mut results);
for p in &results { println!("{:?}", p); }
// [5, 4, 11, 2]
// [5, 8, 4, 5]
}Maximum Path Sum — Any Node to Any Node
The maximum path through a node can include both children. The return-up trick: the helper returns the best single-arm extension (for the parent to use), but updates a global maximum that considers both arms combined at the current node.
fn max_path_sum(root: &Option<Box<TreeNode>>) -> i32 {
fn dfs(node: &Option<Box<TreeNode>>, best: &mut i32) -> i32 {
match node {
None => 0,
Some(n) => {
let left = dfs(&n.left, best).max(0);
let right = dfs(&n.right, best).max(0);
*best = (*best).max(n.val + left + right); // path through n
n.val + left.max(right) // best single arm upward
}
}
}
let mut best = i32::MIN;
dfs(root, &mut best);
best
}
fn main() {
// -10
// / \
// 9 20
// / \
// 15 7
let tree = build(&[Some(-10),Some(9),Some(20),None,None,Some(15),Some(7)]);
println!("{}", max_path_sum(&tree)); // 42 (15→20→7)
let tree2 = build(&[Some(1),Some(2),Some(3)]);
println!("{}", max_path_sum(&tree2)); // 6
}Diameter of a Binary Tree
The diameter through a node is left_height + right_height. Use the same return-up shape: the helper returns height, the outer variable tracks the running maximum diameter.
fn diameter(root: &Option<Box<TreeNode>>) -> i32 {
fn height(node: &Option<Box<TreeNode>>, best: &mut i32) -> i32 {
match node {
None => 0,
Some(n) => {
let l = height(&n.left, best);
let r = height(&n.right, best);
*best = (*best).max(l + r);
1 + l.max(r)
}
}
}
let mut best = 0;
height(root, &mut best);
best
}
fn main() {
// 1
// / \
// 2 3
// / \
// 4 5
let tree = build(&[Some(1),Some(2),Some(3),Some(4),Some(5)]);
println!("{}", diameter(&tree)); // 3 (4→2→1→3 or 5→2→1→3)
}Lowest Common Ancestor
The LCA of nodes p and q is the deepest node that has both as descendants (a node is a descendant of itself). Post-order: if the current node is p or q, return it. If both children return non-null, the current node is the LCA.
fn lca<'a>(node: &'a Option<Box<TreeNode>>, p: i32, q: i32) -> Option<i32> {
match node {
None => None,
Some(n) => {
if n.val == p || n.val == q { return Some(n.val); }
let left = lca(&n.left, p, q);
let right = lca(&n.right, p, q);
match (left, right) {
(Some(_), Some(_)) => Some(n.val), // current node is LCA
(Some(v), None) | (None, Some(v)) => Some(v),
(None, None) => None,
}
}
}
}
fn main() {
// 3
// / \
// 5 1
// / \ / \
// 6 2 0 8
// / \
// 7 4
let tree = build(&[Some(3),Some(5),Some(1),Some(6),Some(2),Some(0),Some(8),None,None,Some(7),Some(4)]);
println!("{:?}", lca(&tree, 5, 1)); // Some(3)
println!("{:?}", lca(&tree, 5, 4)); // Some(5)
println!("{:?}", lca(&tree, 6, 4)); // Some(5)
}Flatten Binary Tree to Linked List
Flatten in-place to a right-skewed tree (pre-order). The trick: for each node, store its right child, connect the left subtree as the right child, find the tail of that subtree, then attach the stored right child. Works right-to-left if you track the previously processed node.
fn flatten(node: &mut Option<Box<TreeNode>>) {
// Collect pre-order values, rebuild as right-skewed tree
fn preorder(n: &Option<Box<TreeNode>>, vals: &mut Vec<i32>) {
if let Some(node) = n {
vals.push(node.val);
preorder(&node.left, vals);
preorder(&node.right, vals);
}
}
let mut vals = Vec::new();
preorder(node, &mut vals);
fn rebuild(vals: &[i32]) -> Option<Box<TreeNode>> {
if vals.is_empty() { return None; }
Some(Box::new(TreeNode { val: vals[0], left: None, right: rebuild(&vals[1..]) }))
}
*node = rebuild(&vals);
}
fn print_right_skew(node: &Option<Box<TreeNode>>) {
let mut curr = node;
let mut first = true;
while let Some(n) = curr {
if !first { print!(" -> "); }
print!("{}", n.val);
first = false;
curr = &n.right;
}
println!();
}
fn main() {
// 1
// / \
// 2 5
// / \ \
//3 4 6
let mut tree = build(&[Some(1),Some(2),Some(5),Some(3),Some(4),None,Some(6)]);
flatten(&mut tree);
print_right_skew(&tree); // 1 -> 2 -> 3 -> 4 -> 5 -> 6
}Validate Binary Search Tree
Pass down the valid range (min, max) at each node. The root has no constraints; going left tightens the upper bound; going right tightens the lower bound.
fn is_valid_bst(node: &Option<Box<TreeNode>>, min: i64, max: i64) -> bool {
match node {
None => true,
Some(n) => {
let v = n.val as i64;
v > min && v < max
&& is_valid_bst(&n.left, min, v)
&& is_valid_bst(&n.right, v, max)
}
}
}
fn main() {
// 2
// / \
// 1 3
let tree = build(&[Some(2),Some(1),Some(3)]);
println!("{}", is_valid_bst(&tree, i64::MIN, i64::MAX)); // true
// 5
// / \
// 1 4
// / \
// 3 6
let tree2 = build(&[Some(5),Some(1),Some(4),None,None,Some(3),Some(6)]);
println!("{}", is_valid_bst(&tree2, i64::MIN, i64::MAX)); // false (4 < 5)
}