Read this before the problems

Almost every tree problem is the same three lines

A tree recursion has three parts and only three. Handle the empty case, ask the same question of both children, and combine their answers with whatever this node contributes. Depth, inversion, validation, ancestors and path sums are all that shape. What differs is the combining line.

Making the empty node the base case rather than the leaf is worth doing every time. A leaf is not a special kind of node, it is a node whose children happen to be empty, so it needs no branch of its own. Code that special-cases leaves is usually twice as long and still needs the null check.

The practical consequence is that you should stop trying to remember tree problems individually. Remember the walk, then ask one question about the problem in front of you: what does a node need from its children, and what does it owe its parent. Those two answers are the solution.

Which way the information travels

The fastest way to classify an unfamiliar tree question is to ask which direction information moves in, because that decides the shape of your code before you have written any.

Sometimes it moves down. A node needs context from its ancestors, so you pass extra arguments into the recursive call. Validating a binary search tree works this way: the allowed range is narrowed on the way down, and the node can only be judged once it knows what its ancestors permit. This is a pre-order algorithm, because the work happens before the children are visited.

More often it moves up. A node needs results from its subtrees, so the recursive call returns something and the node combines what comes back. Depth, lowest common ancestor and maximum path sum all work this way. This is post-order, because the work happens after the children report.

A few problems move information in both directions at once, and those are the genuinely hard ones. But most are cleanly one or the other, and deciding which before you start saves you from writing a function that tries to do both and does neither well.

What you return and what you record are different things

This is the idea that separates easy tree problems from hard ones, and it is worth learning deliberately rather than discovering it during an interview.

In simple problems the value a node computes is also the value it hands to its parent. Depth works like that: the depth of a subtree is exactly what the parent needs. In harder problems those two quantities come apart.

Maximum path sum is the clearest example. The best path through a node may descend into both subtrees, bending at the top. But a path that continues up to the parent enters this node once and leaves once, so it can use at most one child. The bent value is a candidate for the answer and gets recorded. The straight value is what the parent can legitimately use and gets returned. Return the bent one and the parent builds a path that visits a node twice, which is not a path at all.

The same split appears in diameter, in longest univalue path, and in most problems where the answer is about a path rather than a node. Once you have seen it, the recognition is instant: if the parent cannot use what the node computed, you need two quantities, not one.

The traversal orders, and when the choice matters

Pre-order visits a node before its children, in-order visits the left subtree then the node then the right, and post-order visits both children before the node. Level order is different in kind: it uses a queue rather than the call stack and reads the tree row by row.

For many problems the choice does not matter. Inverting a tree gives the same result whether you swap before or after recursing, because the swap does not depend on anything below. It is worth knowing when the order is free, so you do not waste time deliberating.

For others it is the whole problem. In-order on a binary search tree produces a strictly increasing sequence, which is why so many BST questions reduce to a single in-order walk with a comparison against the previous value. Post-order is forced whenever a node needs its childrens results. Pre-order is forced when children need the parents context.

Level order earns its place when the question mentions levels, or asks for the shortest path in an unweighted setting, or needs to stop as soon as something is found. Those cannot be answered depth first without awkward bookkeeping, and the queue makes them straightforward.

Costs, and the answer that is usually wrong

Nearly every single-pass tree algorithm is O(n) in time, because it visits each node once and does constant work there. That part is rarely interesting.

The space is where people answer wrongly. A recursive tree walk uses stack space proportional to the height of the tree, not to a constant. For a balanced tree the height is about log n, which is what most people say. For a degenerate tree, one that has become a linked list, the height is n and the stack is linear. Saying O(h) and then explaining that h ranges from log n to n is the answer that shows you understand it.

Breadth-first is different again. Its space is the widest level rather than the height, and in a complete tree the bottom row holds roughly half the nodes, so it is O(n) in the worst case even for a perfectly balanced tree. Depth-first and breadth-first are not interchangeable on memory, and on a wide shallow tree depth-first uses far less.

One trap is worth naming. Any algorithm that recomputes a subtree property at every node, rather than collecting it on the way back up, is quadratic. That is the difference between the brute force and the real solution in maximum path sum, and the same trap appears in diameter and in most path problems.

Where tree code actually goes wrong

The mistakes cluster, and they are the same handful across the whole chapter.

Overwriting before reading. Any problem that rewires pointers can destroy the subtree it still needs, and inversion is the smallest example. Compute both recursive results into temporaries before assigning either. Python hides this behind tuple assignment, which is convenient and also why people are surprised when the Java version breaks.

Checking only the parent and child. Being a binary search tree is a property of every ancestor, not the nearest one, so a local comparison passes on trees that are visibly invalid. Whenever a property involves a whole subtree, the check needs information carried down or brought up, never just the adjacent pair.

Reading the queue size inside the loop. In level order the width has to be frozen before children are pushed, or the row being read absorbs the row being built and every level after the first is wrong.

Seeding a running maximum at zero. When values can be negative the answer can be negative, and zero silently wins. Seed at negative infinity and clamp only the contributions that are genuinely optional, which means child gains and never the node itself.

Now work the problems

These seven are ordered so each one adds a single idea to the one before it. The first two share a shape, the third changes how you travel, and the last three each add a way for information to move.

1. Maximum Depth of Binary TreeLC 104 · Post-order · answer built from children
2. Invert Binary TreeLC 226 · Post-order · same walk, different work
3. Binary Tree Level Order TraversalLC 102 · BFS · one row at a time
4. Validate Binary Search TreeLC 98 · Pre-order · pass bounds down
5. Lowest Common Ancestor of a Binary TreeLC 236 · Post-order · report findings upward
6. Construct Binary Tree from Preorder and InorderLC 105 · Divide and conquer · split by the root
7. Binary Tree Maximum Path SumLC 124 · Post-order · return one thing, record another