Pattern 15 of 27

Tree DFS

Solve a tree problem by asking each subtree for an answer and combining the left and right results at the parent.

Cost: O(n) time, O(h) space for the recursion stack
Problems: 6

When to reach for it

The answer at a node depends on the answers for its children.
The prompt mentions depth, height, paths, or subtrees.
Every node has to be visited and order within a level does not matter.

How it works

Recursive DFS on a tree becomes straightforward once you decide exactly what each call returns. Height returns a number and Path Sum returns whether a path exists. Some problems need two things at once: a value the parent can extend, and a global best for a path that bends through the current node, which is the shape of both Diameter and Maximum Path Sum. With the return value pinned down, the base case and the combine step usually follow directly.

The template

Written for Diameter of Binary Tree (write-up)

def diameter_of_binary_tree(root):
    best = 0

    def height(node):
        nonlocal best
        if not node:
            return 0
        left, right = height(node.left), height(node.right)
        best = max(best, left + right)   # path that bends at this node
        return 1 + max(left, right)      # what the parent can extend

    height(root)
    return best

Open in the editor Trace it line by line

Six problems, in learning order

1.Maximum Depth of Binary TreeLeetCode 104Return one plus the depth of the deeper child.Easy
2.Path SumLeetCode 112Subtract each node's value on the way down and check the remainder at a leaf.Easy
3.Path Sum IILeetCode 113The Path Sum walk, backtracking a list of the nodes on the path.Not in the curated 370 yet.Medium
4.Diameter of Binary TreeLeetCode 543A global best of left plus right, returning the taller side to the parent.Easy
5.Binary Tree Maximum Path SumLeetCode 124Diameter with node values, ignoring branches whose best sum is negative.Hard
6.Invert Binary TreeLeetCode 226Swap the children, then recurse into both.Easy

What usually goes wrong

Confusing what the function returns with the global answer it updates along the way.
Very deep, skewed trees exceeding Python's default recursion limit of 1000.
Extending a path through a negative subtree instead of cutting it off at zero.

Tree DFS, answered

When should I use the tree dfs pattern?

The answer at a node depends on the answers for its children. The prompt mentions depth, height, paths, or subtrees. Every node has to be visited and order within a level does not matter.

What is the time complexity of tree dfs?

O(n) time, O(h) space for the recursion stack. With the return value pinned down, the base case and the combine step usually follow directly.

Which problem should I start with for tree dfs?

Start with Maximum Depth of Binary Tree (LeetCode 104, Easy). Return one plus the depth of the deeper child. The six problems on this page are in learning order.