LC 104 · Easy · Post-order · answer built from children

Maximum Depth of Binary Tree

The answer at a node is a simple combination of the same answer at its children.

Recognise it

Before any code, what in the question tells you this is the pattern?

Any question of the form "how deep", "how tall", "how many levels". More generally, any question whose answer at a node is a simple combination of the same answer at its children. This is the base shape every other tree recursion is a variation of.

The brute force

Always have this one ready. It is the honest starting point, and it is what the real solution improves on.

Walk every root-to-leaf path, count the nodes on each, and keep the longest. You can do this by carrying a path list down the tree and recording its length whenever you reach a leaf.

O(n) time, but O(n) extra space for the paths, and considerably more code.

It is not slower in the way a brute force usually is. It is worse because it computes far more than the question asked for. You never need a path, only its length, and a length is a number a child can hand to its parent. Noticing that you are carrying a structure when a scalar would do is the move that turns most tree problems from awkward into three lines.

The approach

The idea in plain language, before it becomes syntax.

Ask the question of the tree and then ask the same question of its parts. How deep is this tree? It is one level for the root, plus however deep the deeper subtree is. That sentence is already the algorithm, and the code is a direct transcription of it.

The base case is the empty tree, which has depth zero. Choosing the null node rather than the leaf as the base is what keeps the code short. A leaf is not special: it is a node whose two children are both empty, so it falls out of the general rule with no extra branch.

This is worth dwelling on because every later problem in this chapter is the same walk with different work at the node. Learn where the recursion goes and what the base case is here, and the rest of the chapter is about what to compute rather than how to travel.

A tree whose depth is one more than the deeper of its two subtrees.Depth is one for this node, plus the deeper side.3920157depth(3) = 1 + max(depth(9), depth(20)) = 1 + max(1, 2) = 3The empty tree has depth 0. A leaf needs no case of its own: both its children are empty.
Maximum Depth of Binary Tree: the idea in one picture.edit source
The three-line shape shared by every tree recursion.if node is null: return the empty answerL = solve(left) R = solve(right)combine L, R and this nodeonly this line changes
Base case, recurse both sides, combine. Only the last line changes between problems.

The algorithm

The same idea again, as steps you could follow with a pencil.

Flowchart for the depth recursion.node is null ?yesreturn 0noL = depth(left)R = depth(right)return 1 + max(L, R)
Maximum Depth of Binary Tree: the loop, step by step.edit source
Time O(n)Space O(h) for the call stack, where h is the height

The solution

Now the code, and why each decision in it is the way it is.

maximum_depth_of_binary_tree
def maxDepth(root):
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

Each node is visited exactly once and does constant work, so the running time is linear in the number of nodes. There is no way to do better, because a node you never look at could have been the deepest.

The space is the depth of the call stack, which is the height of the tree. That is O(log n) for a balanced tree but O(n) for a degenerate one, and it is the honest answer to give when asked, rather than claiming O(1).

If the tree can be very deep, an explicit stack avoids blowing the call stack. It is the same algorithm with the recursion made manual, and worth mentioning out loud even if you do not write it.

Depth counted from the root against height counted from the leaves.depthmeasured downward from the rootheightmeasured upward from the leavesInterviewers use both words loosely. Say which one you mean before you code.
Interviewers use both words loosely. Say which one you mean.

Where people slip

  • The base case is the null node, not the leaf. Handling leaves specially doubles the code and introduces a null check you still need anyway.
  • Return 1 + max(...), not max(1 + ..., 1 + ...). Both work here, but the first says "this node contributes one level" which is the idea you want to carry to harder problems.
  • Recursion depth is the tree height, so a skewed tree of 105 nodes can overflow the stack in languages without deep stacks.

Your notes

What tripped you up here? Write it in your own words.

Where interviewers go next

Solve this one and the follow-up is usually a variation rather than a new idea. Knowing the connection is worth more than memorising each problem.

  • Balanced Binary TreeLC 110Same walk, but return the height AND a validity flag together, so one pass answers both.
  • Minimum DepthLC 111Looks symmetric but is not. A null child is not a leaf, so a one-sided node must not report depth 1.
  • Diameter of Binary TreeLC 543The first problem where what you return upward differs from what you record globally.