11. Tree DFS / DP-on-Trees

TL;DR

Depth-first search on trees visits each subtree once, carrying state down (bounds for BST checks, path aggregates) and bubbling structured answers up the recursion stack. The DP-on-tree trick is post-order: each node returns a compact summary about its subtree while also updating a global or outer best that may cross through the node (diameter, max path sum). Pair pre/in/post-order with either recursion or explicit stacks; LCA is finding where subtrees first meet under a common ancestor.

Recognition Cues

Phrases: “height,” “diameter,” “path sum,” “balanced,” “validate BST,” “lowest common ancestor,” “sum/count in subtree,” “kth in BST,” “same structure.”
Inputs: tree nodes with left/right (or children), sometimes BST ordering.
Outputs: a single scalar optimum, a boolean property, or a specific node (LCA).

Diagram

Pattern control flow (customize nodes for this pattern). camelCase node IDs.

Loading diagram…

Mental Model

Walk one branch to the leaf, then combine children results at each node. For “best path that might bend at this node,” keep two quantities: the best answer seen anywhere so far (often unconstrained) and the best rooted chain through this node that parents can still extend. BST validation is DFS with open intervals (minBound, maxBound) tightening as you go left/right. LCA is “first node where p and q split into different subtrees,” or a node equals p/q.

Generic Recipe

Choose order: pre-order (push state before children), post-order (aggregate after children), in-order on BST for sorted sequence.
For DP-on-tree: at each node, compute child summaries; combine into bestThroughHere and update bestOverall if the problem allows paths that turn at this node.
For BST bounds: pass minBound / maxBound; left child must be < node.val, right > node.val (or equal per problem definition).
For LCA (general binary tree): if current is p or q, return it; else recurse; if both subtrees return non-nil, current is LCA; else return the non-nil side.
Iterative: use explicit stacks; post-order often needs last visited tracking or two stacks / processed flags.

Complexity

Time: O(n) nodes visited once per DFS pass; multiple passes still linear if constant passes.
Space: O(h) recursion stack or explicit stack, h = height; O(n) worst on skewed tree.

Generic Code Template

Go

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func dfsPostorderDP(root *TreeNode) (bestOverall int, bestRooted int) {
	if root == nil {
		return 0, 0
	}
	leftOverall, leftRooted := dfsPostorderDP(root.Left)
	rightOverall, rightRooted := dfsPostorderDP(root.Right)
	bestThroughNode := leftRooted + rightRooted + root.Val
	bestOverall = leftOverall
	if rightOverall > bestOverall {
		bestOverall = rightOverall
	}
	if bestThroughNode > bestOverall {
		bestOverall = bestThroughNode
	}
	bestRooted = root.Val
	if leftRooted+root.Val > bestRooted {
		bestRooted = leftRooted + root.Val
	}
	if rightRooted+root.Val > bestRooted {
		bestRooted = rightRooted + root.Val
	}
	return bestOverall, bestRooted
}

func validateBSTBounds(root *TreeNode, minBound int, maxBound int) bool {
	if root == nil {
		return true
	}
	if root.Val <= minBound || root.Val >= maxBound {
		return false
	}
	return validateBSTBounds(root.Left, minBound, root.Val) &&
		validateBSTBounds(root.Right, root.Val, maxBound)
}

func iterativePreorder(root *TreeNode) []int {
	var result []int
	stack := []*TreeNode{}
	if root != nil {
		stack = append(stack, root)
	}
	for len(stack) > 0 {
		lastIndex := len(stack) - 1
		node := stack[lastIndex]
		stack = stack[:lastIndex]
		result = append(result, node.Val)
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
	}
	return result
}

func iterativeInorder(root *TreeNode) []int {
	var result []int
	stack := []*TreeNode{}
	current := root
	for current != nil || len(stack) > 0 {
		for current != nil {
			stack = append(stack, current)
			current = current.Left
		}
		lastIndex := len(stack) - 1
		node := stack[lastIndex]
		stack = stack[:lastIndex]
		result = append(result, node.Val)
		current = node.Right
	}
	return result
}

func iterativePostorder(root *TreeNode) []int {
	var result []int
	var stack []*TreeNode
	var lastVisited *TreeNode
	current := root
	for current != nil || len(stack) > 0 {
		if current != nil {
			stack = append(stack, current)
			current = current.Left
		} else {
			peek := stack[len(stack)-1]
			if peek.Right != nil && lastVisited != peek.Right {
				current = peek.Right
			} else {
				stack = stack[:len(stack)-1]
				result = append(result, peek.Val)
				lastVisited = peek
			}
		}
	}
	return result
}

JavaScript

function dfsPostorderDP(root) {
  if (!root) return { bestOverall: 0, bestRooted: 0 };
  const left = dfsPostorderDP(root.left);
  const right = dfsPostorderDP(root.right);
  const bestThroughNode = left.bestRooted + right.bestRooted + root.val;
  const bestOverall = Math.max(
    left.bestOverall,
    right.bestOverall,
    bestThroughNode
  );
  const bestRooted = Math.max(
    root.val,
    root.val + left.bestRooted,
    root.val + right.bestRooted
  );
  return { bestOverall, bestRooted };
}

function validateBSTBounds(root, minBound, maxBound) {
  if (!root) return true;
  if (root.val <= minBound || root.val >= maxBound) return false;
  return (
    validateBSTBounds(root.left, minBound, root.val) &&
    validateBSTBounds(root.right, root.val, maxBound)
  );
}

function lowestCommonAncestor(root, first, second) {
  if (!root || root === first || root === second) return root;
  const left = lowestCommonAncestor(root.left, first, second);
  const right = lowestCommonAncestor(root.right, first, second);
  if (left && right) return root;
  return left ?? right;
}

function iterativeInorder(root) {
  const result = [];
  const stack = [];
  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;
}

Variants

Pure traversal (invert, max depth, paths): any order; collect or mutate as needed.
BST-only tricks: in-order → sorted array; LCA using value comparisons without full tree search.
Serialize/deserialize: preorder with null markers; build tree from preorder + inorder with index ranges.
Iterative post-order: stack + lastVisited pointer, or push (node, state) tuples.

Representative Problems

236. Lowest Common Ancestor of a Binary Tree — LCA pattern
98. Validate Binary Search Tree — DFS with bounds
124. Binary Tree Maximum Path Sum — two-value DP-on-tree
543. Diameter of Binary Tree — best-through-node vs rooted height

Anti-patterns

Using global mutable state without a clear invariant (harder to port to iterative / parallel reasoning).
Passing min/max as node values without strict < / > rules — duplicates break naive BST checks.
Computing diameter as only leftHeight + rightHeight without updating a global max at each node (path might not pass current root in some definitions — usually height-based formulation still works if you define height correctly).
LCA on BST using general binary-tree LCA without exploiting ordering when it would simplify the code.

On this page