cf.completefrontend
TREES & TRIES · CORE

Tree dynamic programming

Solve a tree problem by computing an answer for each subtree from its children's answers, bottom up.

Time O(n)Space O(h)9 practice problemsStep-through picture

The idea

Many tree questions are about a best or total value: the longest path, the biggest sum, the fewest items to cover every node. Trying every choice would take far too long. Tree dynamic programming (tree DP) breaks the problem into one small question per node: "what is the best answer for my subtree?"

A node answers that question using only the answers of its children. A postorder walk (children first, then the node) makes sure those answers are ready. Each node's answer is computed once and reused by its parent.

Often the value a node returns to its parent is different from the final answer. For the longest path between two nodes, a node returns its height (one branch going down), but it also checks a path that bends through itself, using both children, and keeps the best one in a variable outside the recursion.

An everyday example

Counting votes from the bottom of an organization

A company wants a total from every team. Each team lead waits for reports from the people directly under them, adds their own number, and sends one total up to their manager. Nobody needs the whole company's data, only their direct reports' totals. When the reports reach the top, the CEO has the answer.

How the example maps to the code
In the exampleIn the code
A team lead waiting for reportsconst left = height(node.left) and const right = height(node.right)
Sending one total upreturn 1 + Math.max(left, right)
A note on the side about the best team seenbest = Math.max(best, left + right)
Someone with no reportsnode === null, which returns 0

From the slow way to tree dynamic programming

  1. Say you want the longest path between any two nodes, counted in edges. The obvious way: for every pair of nodes, find the path between them and measure it. With n nodes there are about n² / 2 pairs, and measuring each path can cost up to O(n), so the whole thing is O(n³).
  2. Every path has one highest node, where it stops going up and starts going down. So instead of looking at pairs, ask one question per node: what's the longest path whose highest point is right here? That path goes as far down the left side as it can and as far down the right side as it can.
  3. "As far down as it can" from a child is that child's height. And a node's height comes straight from its children's heights: 1 + Math.max(left, right). So if every node is handled after its children, which is postorder, each node finds its children's heights ready and needs only constant work.
  4. One walk then does both jobs. Each call returns its height to the parent and, on the side, updates best with left + right, the longest path that bends at this node. A postorder walk where each node computes its answer from its children's answers is tree DP.

How it works

  1. Decide what each node returns to its parent. Here height(node) returns the number of nodes on the longest downward path.
  2. Handle the empty subtree: height(null) is 0.
  3. Compute the children's answers first: left = height(node.left) and right = height(node.right).
  4. Use them to check the answer that bends through this node: a path down both sides has left + right edges. Update best.
  5. Return this node's value for its parent: 1 + Math.max(left, right), because a parent can extend only one branch.
  6. Call height(root) once and return best.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function longestPath(root) {
  2. let best = 0;
  3. function height(node) {
  4. if (node === null) return 0;
  5. const left = height(node.left);
  6. const right = height(node.right);
  7. best = Math.max(best, left + right);
  8. return 1 + Math.max(left, right);
  9. }
  10. height(root);
  11. return best;
  12. }

How fast it is

TimeO(n)
Extra memoryO(h)

Each node does a constant amount of work once its children report back. The recursion holds one call per level of the current path.

  • Best caseO(n)

    Any tree, even a single node: every node must report its height once.

  • Average caseO(n)

    A random tree: one visit per node, with constant work each.

  • Worst caseO(n)

    A chain of n nodes: still one visit per node, but the recursion is as deep as the tree.

Common mistakes

  • Returning left + right to the parent. A parent can't use a path that already bends, because it would branch three ways. Return one branch, and record the bent path in best.
  • Mixing up nodes and edges. Here height counts nodes and left + right counts edges. Read the question carefully and test a single-node tree.
  • Starting best at 0 when values can be negative, as in a maximum path sum. Start at -Infinity or at the root's value.
  • Recomputing a child's answer several times, for example by calling a separate height(child) inside another recursive function. That turns O(n) into O(n^2). Compute once and return it.

When to use it

Look for these clues in a problem:

  • The question asks for a maximum, minimum, or count over paths or choices in a tree.
  • The answer for a node can be built from the answers of its children.
  • A path may bend at a node, going down into both children.
  • You must choose nodes under a rule that involves parents and children, like "never pick a node and its parent".

Check yourself

Answer each one in your head first, then open it.

Why can't height simply return the longest path?

A parent can only extend one downward branch of its child. A path that already bends at the child can't be extended upward, so the parent needs the height, and the bent path is recorded separately in best.

In the trace, why is the root's left + right only 4?

The root has no right child, so right = 0, and its left height is 4. The bent path at 4 has 5 edges, so best keeps 5.

How many times is height called on a tree with n nodes?

2n + 1 times: once per node and once per empty child slot.

In what order must the work happen, and why?

Children before their parent, which is postorder, because lines 7 and 8 use left and right, and those are ready only after both recursive calls return.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 9 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Optimal substructure, the fact that a big answer is built from best answers of smaller parts: the longest downward path from a node is the node plus the longer of its children's longest downward paths. A downward path from node goes through exactly one child, so nothing else can make it longer. That makes height(node) = 1 + Math.max(left, right), with height(null) = 0, exact.

The longest path in the whole tree has some highest node top, and from top it goes down the left side, the right side, or both. Each of those parts must be a longest downward path on its side, because otherwise swapping in a longer one would give a longer path. So the best path with highest node top has exactly left + right edges, and checking every node as top covers every path in the tree.

The order of filling is postorder: lines 5 and 6 finish before line 7 reads their results, so each node's inputs are final when it uses them. Every node is computed once and read once by its parent, which is what makes this O(n) instead of the O(n³) of trying all pairs.

Going deeper

3 more ideas

Why each node needs only its children

The longest path through a node goes down some way on its left side and some way on its right side, and the longest way down each side is exactly that child's height. So the best path bending at node has left + right edges. Every path in the tree bends at exactly one highest node, so checking every node covers every path.

Returning two values

Some problems need more than one number per node. To pick nodes with the biggest total where no node is picked together with its parent, each node returns a pair: the best total if it is picked, and the best if it is skipped. If it is picked, its children must be skipped; if it is skipped, each child takes whichever of its two values is bigger.

Time and memory

Each node is visited once and does constant work with its children's answers, so the time is O(n). Memory is the recursion depth, O(h). Without this reuse, trying every path or every choice could be exponential.

Work it by hand

Every step in a table, with why

Find the longest path in a 7-node tree where that path does not go through the root.

root = [9, 4, null, 2, 6, 1, null, null, 7, null, null, null, 8]

StepnodeleftrightbestReturnsWhat happensWhy
110001leafThe walk goes down to 1 first. Both children are null, so left = 0 and right = 0. A path bending here has no edges.
221012best becomes 1A path bending at 2 has 1 + 0 = 1 edge, 1-2. best grows to 1, and 2 reports a height of 2 to its parent.
380011leafNow the right subtree of 4. Postorder reaches the deepest node, 8, first.
4701120 + 1 doesn't beat bestA path bending at 7 has 1 edge, which ties best but doesn't beat it.
560223best becomes 2A path bending at 6 is 6-7-8, 2 edges.
642354best becomes 5The path bending at 4 goes 2 edges down the left and 3 down the right: 1-2-4-6-7-8, 5 edges. This is the answer, and it doesn't touch the root.
7940554 + 0 = 4, keep 5The root has only a left child, so the best path bending at 9 has 4 edges, less than best. The root's return value is not used.

longestPath returns 5. Each of the 7 nodes was handled once, after its children. The trace shows why best must live outside height: the answer was found at 4, but 4 can only send its height up, not the bent path.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Tree dynamic programmingO(n)O(h)The answer for a node comes from its children's answers.
Try every pair of nodesO(n³)O(n)Never for real input. It's the slow starting point this replaces.
Two breadth-first searchesO(n)O(n)Only for the longest path in an unweighted tree given as edges: search from any node to the farthest node a, then from a; the farthest distance is the answer. It doesn't extend to sums or pick-or-skip questions.

Extra memory: O(h) for the call stack plus one number, best. A balanced tree needs about log₂ n waiting calls; a chain needs n.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Tree dynamic programming and the other approaches, on a scale where each line up is 10 times more steps.
  • Tree dynamic programming, Two breadth-first searches O(n)
  • Try every pair of nodes O(n³)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Tree dynamic programming101,0001 million
Try every pair of nodes1,0001 billionmore than a quadrillion
Two breadth-first searches101,0001 million

Inputs that need care

5 tricky inputs
An empty tree: root = null
height(null) returns 0 and best stays 0. Decide whether an empty tree should report 0; this code says it does.
One node
left and right are both 0, so best stays 0: a single node has a longest path of 0 edges.
The longest path avoids the root, as in the trace
This is why best is checked at every node. Using only height(root.left) + height(root.right) would give 4 here instead of 5.
Counting nodes instead of edges
Some questions want the number of nodes on the path. That's best + 1 for a non-empty tree. Decide which before writing the base case.
Negative values in a "biggest path sum" version
A child's branch can then lower the total. Use Math.max(0, childSum) so a node can choose not to extend into a negative branch.

Variations and follow-ups

Twists interviewers add

Biggest path sum

Same shape, with sums instead of heights. Each call returns node.val + Math.max(0, left, right), the best downward sum, and updates best with node.val + Math.max(0, left) + Math.max(0, right). Start best at -Infinity so a tree of all negative values still works.

Pick or skip

For questions like "choose nodes with the biggest total where no parent and child are both chosen", return two numbers per node, take and skip. take = node.val + left.skip + right.skip, and skip = Math.max(left.take, left.skip) + Math.max(right.take, right.skip).

Rerooting

Some questions need the answer as if each node in turn were the root, such as the sum of distances from every node to all others. Do one postorder pass for subtree answers, then a preorder pass that pushes the parent's side down to each child, for O(n) in total.

Trees with many children

With a children array, loop over the children instead of making two calls. For the longest path, keep the two largest child heights instead of left and right.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "maximum" or "minimum" over paths or groups of nodes in a tree, "diameter", "no two adjacent nodes", or "the best subtree". If brute force would try many paths or many choices, think tree DP.
  • Separate two things out loud: "what this call returns to its parent" and "what it records as a possible final answer". Mixing them up is the most common bug.
  • Test on a tree where the answer avoids the root, like the trace, and on a tree that is a single chain.
  • A usual follow-up: "now values can be negative and you want the biggest sum". Clamp each child's contribution at 0 and start best at -Infinity.

Where frontend code uses it

The same idea in real UI code
  • A browser computes many layout sizes bottom up: a box that sizes to its content needs its children's sizes before it knows its own.
  • React's reconciler collects subtreeFlags from children while completing each fiber, so a parent knows whether anything below it needs work. That is a value combined from children, bottom up.
  • A file explorer shows each folder's total size and file count, computed from the totals of its subfolders.
  • A collapsed comment thread shows "12 replies", the size of the subtree under that comment.

Related algorithms