Tree DFS
On this page
Depth-first search on a tree is recursion: solve the problem for the left subtree, solve it for the right subtree, combine. The hard part is not the traversal but deciding which way information flows. Bottom-up, a node needs its children's answers (height, sum, "is this subtree balanced?"). Top-down, a node needs something from above it (the allowed range in a BST, the path so far). Many problems use both: return one thing upward, and record the real answer on the side.
Binary Trees covers traversal orders. This page is about the problem-solving shapes.
When to recognise it
- Height, depth, diameter, balanced, max path sum: facts about a subtree, so bottom-up.
- Validate a BST, "path from root with sum X", "good nodes", "max difference with an ancestor": the node needs context from its ancestors, so top-down.
- Lowest common ancestor: bottom-up. Each call returns "did I find p or q down here?"
- All root-to-leaf paths: top-down with a shared path list, which is backtracking on a tree (see Backtracking).
- Serialize, clone, build from traversals: a pre-order walk.
The two shapes

Bottom-up returns a value from each call:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val, self.left, self.right = val, left, right
def max_depth(node):
if not node:
return 0
return 1 + max(max_depth(node.left), max_depth(node.right))
Top-down passes extra parameters:
def is_bst(node, lo=float('-inf'), hi=float('inf')):
if not node:
return True
if not lo < node.val < hi:
return False
return is_bst(node.left, lo, node.val) and is_bst(node.right, node.val, hi)
Both are O(n) time and O(h) space for the recursion, where h is the height: O(log n) if the tree is balanced, O(n) if it is a chain.
Return one thing, record another
Some answers do not flow up cleanly. The diameter (longest path between any two nodes) may bend at a node, using both children, but a path that continues upward can only use one child. So the helper returns a height and records the best bend in an outer variable.

def diameter(root):
"""Bottom-up with a side answer: return height upward, record the best path through each node."""
best = 0
def height(node):
nonlocal best
if not node:
return 0
l, r = height(node.left), height(node.right)
best = max(best, l + r) # path that bends at this node
return 1 + max(l, r) # only one branch can continue upward
height(root)
return best
Binary Tree Maximum Path Sum is the same shape with sums instead of heights, plus one twist: a child's contribution is max(0, child), because a negative branch is better left out.
Top-down with a path
When you need the actual paths, keep one list, add the node on the way down and remove it on the way back:
def root_to_leaf_paths(root, target):
"""Top-down with backtracking: the path list is shared, so undo after each child."""
out, path = [], []
def go(node, remaining):
if not node:
return
path.append(node.val)
if not node.left and not node.right and remaining == node.val:
out.append(path[:]) # copy, the list keeps changing
go(node.left, remaining - node.val)
go(node.right, remaining - node.val)
path.pop()
go(root, target)
return out
Common bugs
- Validating a BST by comparing a node only with its children. A node deep in the left subtree must also be smaller than the root. Pass
(lo, hi)down. - Returning the answer instead of the helper value: for diameter or max path sum, the function returns a height (or one-branch sum), not the answer.
- Appending
pathinstead ofpath[:]: every saved path ends up as the same, finally empty, list. - Forgetting to undo (
path.pop()), so paths leak into siblings. - Recursion depth on a chain of 10⁵ nodes. Python's default limit is about 1,000. Mention an iterative version with an explicit stack, or
sys.setrecursionlimit.
Say this in the interview
- "Each call returns the height of its subtree. At every node I also check the path that bends here, left plus right, and keep the best. Every node is visited once: O(n) time, O(h) stack."
- "For the BST check I pass the allowed range down, because the rule is about all ancestors, not only the parent."
Problems for this pattern
- Maximum Depth of Binary Tree: bottom-up, one line.
- Invert Binary Tree: swap children at every node.
- Diameter of Binary Tree: return height, record the bend.
- Validate Binary Search Tree: top-down ranges.
- Lowest Common Ancestor of a Binary Tree: bottom-up "found it" flags.
- Kth Smallest Element in a BST: in-order DFS, stop at the k-th node.
- Construct Binary Tree from Preorder and Inorder Traversal: pre-order gives the root, in-order splits the subtrees.
- Binary Tree Maximum Path Sum: diameter with sums.
- Serialize and Deserialize Binary Tree: preorder with null markers, read back in the same order.
- Flatten a Nested JSON Object: DFS that carries the key path down.
Related
Binary Trees · Binary Search Trees · Tree BFS · Backtracking · Graph BFS and DFS