dsa.university
start_free
Blog/TREES

Most tree problems are post-order with a return value

Once you see the skeleton, tree problems stop being individually hard. Six problems, one shape, and the only thing that ever changes.

LH
Dr. Lena HoffCurriculum lead
13 July 2026·6 min read

There is a moment in the trees track where a large fraction of the material collapses into one idea, and after that the problems stop feeling individually difficult. The idea is that most tree problems are the same six-line recursion with a different combine step.

The skeleton

python
1def solve(node):
2 if not node:
3 return BASE
4 left = solve(node.left)
5 right = solve(node.right)
6 return COMBINE(left, right, node)

Recurse both sides, then combine. Everything below is that skeleton with BASE and COMBINE filled in.

Maximum depth

python
1BASE = 0
2COMBINE = 1 + max(left, right)

Balanced check

Return the height, or −1 as a sentinel meaning 'already unbalanced'. Propagating the failure through the return value avoids computing heights twice.

python
1def height(node):
2 if not node:
3 return 0
4 l = height(node.left)
5 r = height(node.right)
6 if l == -1 or r == -1 or abs(l - r) > 1:
7 return -1
8 return 1 + max(l, r)

Diameter

Here the return value and the answer are different things, and that is the second idea worth internalising. Each call returns the height, while updating a running best with left + right — the path through this node. A node's best path is not what its parent needs to know.

python
1best = 0
2
3def height(node):
4 global best
5 if not node:
6 return 0
7 l, r = height(node.left), height(node.right)
8 best = max(best, l + r) # answer: path through this node
9 return 1 + max(l, r) # return: what the parent needs
The general move

When the answer at a node is not the value the parent needs, return the parent's value and accumulate the answer on the side. Diameter, maximum path sum and longest consecutive sequence are all this.

Maximum path sum

Same structure again. The return value is the best downward path — you may only extend through one child. The accumulated answer may bend at this node and use both.

python
1def gain(node):
2 global best
3 if not node:
4 return 0
5 l = max(gain(node.left), 0) # negatives are refused
6 r = max(gain(node.right), 0)
7 best = max(best, node.val + l + r)
8 return node.val + max(l, r)

When it is not post-order

Some tree problems genuinely need information flowing downward — validate BST needs the interval from ancestors; path-sum-from-root needs the running total. Those are pre-order with a parameter rather than post-order with a return value, and they are the smaller family.

The diagnostic question is short: does this node's answer depend on what is above it, or only on what is below it? Below only means post-order with a return value. Above means pass state down. Both means both, and there are only a handful of those.

treerecursionpatterns
Practise this

Reading about a pattern is not the same as producing it under time pressure. The problems that drill this are in the curriculum, in order.

open_curriculumcreate_account
previousBinary search on the answer, not on the arraynext Union-Find: the two optimisations and why both matter

Related reading.

TREES

Why your BST validation passes the samples and dies on depth

7 min readFUNDAMENTALS

Reading a call stack without a debugger

7 min readFUNDAMENTALS

Recursion to iteration, without breaking the base case

7 min read