Bottom-Up Return Values (the Manager)

In the bottom-up style the parent waits for its children to report, then decides. Think of each node as a manager: it can't answer until its team has. Height, diameter, balance and maximum path sum all follow this shape, and they are all postorder walks.

The idea#

Each call answers one question about its subtree and returns it: height = 1 + max(left_height, right_height). Every node is visited once and does $O(1)$ work on top of its children's answers, so the whole walk is $O(n)$ .

The harder problems add one twist. What you compute at a node is not always what you return to its parent. A path through a node may use both sides. The parent, though, can only extend a path that goes down one side. So you keep the "through this node" answer in an outer variable and return the "extendable" value.

For every problem, ask two questions before you code:

What should the current call compute (and record as a candidate answer)?
What should it return to its parent?

How to spot it#

The answer for a node depends on the answers for its subtrees.

"Height", "depth", "size", "is balanced", "diameter".
"Longest path" or "maximum path sum" where the path may bend at any node.
A path that starts and ends anywhere (not only at the root or a leaf).
A decision that depends on subtree sizes or counts.

Template#

Here are those two questions as code: the outer variable holds what you compute, and the return line holds what the parent gets. Nodes follow LeetCode's TreeNode(val, left, right).

best = starting value                # outer variable for the answer
solve(node):
    if node is None: return the empty-subtree value
    left = solve(node.left)
    right = solve(node.right)
    best = better of best and the answer that uses node, left and right
    return the one-sided value the parent can extend
solve(root)
return best

When every node's answer is the answer itself (height, size), the outer variable goes away and you return the value directly.

Why one pass matters#

The template does both jobs in one walk, and that is on purpose. A first attempt often calls a separate helper (such as "best downward path") from every node. That recomputes each subtree once per ancestor and costs $O(n^2)$ on a skewed tree. Fold the candidate update into the same postorder walk, and the cost drops back to $O(n)$ .

Pitfalls#

These mistakes give wrong paths or wrong signs.

Returning the answer instead of the extendable value. If a node returns the two-sided answer, the parent builds paths that fork, and those aren't paths.
Starting best at 0 when values can be negative. Start from root.val (or -inf) instead.
Keeping a branch that only hurts. When you sum along a path, a branch with a negative total drags the sum down. Clip it to 0.
Edge cases. No root, no left child, no right child. Decide what each returns before you write the recursion.

When the answer needs history from the root instead, see Top-Down State and Path Prefix Sums. When a node must return several states at once, see Tree DP with States.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first two.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Maximum Depth of Binary Tree

No outer variable needed. An empty node returns 0, and every other node returns 1 + max(left, right).

Hint: Balanced Binary Tree

Return the height, so the parent can compare its two children. Set a flag on the side when abs(left - right) > 1. Once the flag is set, you can stop early by returning right away.

Hint: Diameter of Binary Tree

The longest path through a node is left + right; record it in best. The parent can extend only one side, so return 1 + max(left, right).

Hint: Binary Tree Maximum Path Sum

Same shape as the diameter, with one extra rule: clip each child's gain with max(0, ...), because a negative branch only hurts. Record node.val + left + right and return node.val + max(left, right). Start best at root.val, since every value may be negative.

Hint: Longest Univalue Path

Return the length of the longest one-sided arm of equal values going down. A child's arm counts only when the child has the same value as the node; otherwise it counts as 0. Record the two arms added together as the candidate.

Hint: Binary Tree Coloring Game

Your best move is to block the opponent's node x: take its left child, its right child or its parent, and you own that whole region. Count left = size(x.left) and right = size(x.right); the parent side is n - left - right - 1. You win if any of the three regions holds more than n // 2 nodes.

Hint: Same Tree

Two trees match when both roots are empty, or both exist with equal values and matching left and right subtrees. Return that boolean from every call.

Key takeaways#

Bottom-up means postorder: the parent waits for both children.
Separate what a node computes from what it returns.
Keep the best "through this node" answer in an outer variable.
Clip negative branches to 0 when summing paths.
One postorder pass is $O(n)$ ; calling a helper from every node is $O(n^2)$ .

Core idea#

In the bottom-up style, the parent waits for its children to report, then decides. What a node computes is not always what it returns to its parent.

Key points#

Bottom-up means postorder.
Each call answers one question about its subtree, for example height = 1 + max(left, right).
One visit per node with $O(1)$ extra work gives $O(n)$ .
Before you code, ask: what does the call compute, and what does it return?
Diameter: the path through a node uses left + right. The parent can extend only one side, so return 1 + max(left, right).
Keep the best "through this node" answer in an outer variable.
Max path sum: clip a negative branch to 0 before you use it.
Balanced tree: return the height and set a flag when abs(left - right) > 1.
Spot it: height, size, balanced, diameter, a path that can bend at any node.

Template#

best = starting value                # root.val if values can be negative
solve(node):
    if node is None: return 0
    left = max(0, solve(node.left))  # drop a losing branch (path sums)
    right = max(0, solve(node.right))
    best = max(best, node.val + left + right)  # compute: bends here
    return node.val + max(left, right)         # return: one side
solve(root)
return best

Pitfalls#

Returning left + right. The parent then builds forked paths, which are not paths.
Starting best at 0 when values can be negative. Start at root.val or -inf.
Calling a "best downward path" helper from every node. That is $O(n^2)$ on a skewed tree.
Edge cases. Decide what no root, no left and no right return before you write the recursion.

Say it in an interview#

"Each node computes the path that bends here, but returns the one-sided path the parent can extend."
"It is one postorder pass, so O(n)."