</> MAANG.io
Sign in
Level101201301
coding interview · 101

Foundations

Master coding interviews with comprehensive coverage of data structures, algorithms, and problem-solving techniques. Progress from fundamentals to advanced topics with expertly curated content.

0/255 solved 0% complete

Divide and Conquer on Trees

What is this?

Lots of hard-looking tree questions melt away with one habit: solve the small pieces first, then combine. You visit the deepest nodes, get an answer for each little branch, and let those answers bubble back up to their parent — the way you'd add up the cost of every room to get the cost of a whole house. Each spot in the tree returns one number upward while quietly keeping score of the best answer seen so far.

flowchart TD A["Visit a node"] --> B["Solve the left branch"] A --> C["Solve the right branch"] B --> D["Combine both results"] C --> D D --> E["Return one value to the parent"]

💡 Fun fact: This bottom-up combining is a baby version of dynamic programming — you compute each subproblem exactly once, so even a giant tree is solved in a single sweep.

🔓 The 6 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: A huge family of tree problems is solved by one move: a post-order DFS where each call returns a single value to its parent, while updating a shared (global/nonlocal) answer that may combine both children. The return value is what a parent can extend; the answer is what bends at the current node. Spotting which information flows up (returned) versus down (passed as arguments) is the whole skill.

The pattern

The dfs template: recurse on both children, update the global answer with combine(L, R, node) using both branches (the bend), and return contribution_to_parent(L, R, node), one branch upward

The recurring tension: a parent can only continue one branch through a child, but the optimal answer often uses both branches meeting at a node. So you return one, but score with both.

The problems

Problem family map: DnC on trees splits into bottom-up problems (Diameter, Max Path Sum, Longest Univalue Path, Smallest Subtree of Deepest Nodes, LCA II) and top-down (Max Diff Node-Ancestor)

  • Diameter, Max Path Sum, Longest Univalue Path — the canonical trio: return an arm/height/gain upward, update the answer with left + right.
  • Smallest Subtree with all the Deepest Nodes — return a richer tuple (depth, covering-node); equal child depths mean this node is the answer.
  • LCA II — fuse an existence check into the search with a found-counter, trusting the result only if both targets were truly seen.
  • Maximum Difference Between Node and Ancestor — the mirror image: information flows down (carry the path min/max as arguments).

Key takeaways

  • Post-order DFS: return one thing, update another — the engine behind diameter, path sum, and more.
  • Return one branch upward; the answer may bend using both branches at a node.
  • Richer return types (tuples, counters) collapse multi-pass solutions into one O(n) pass.
  • Direction matters: bottom-up returns info; top-down carries info down as arguments.
  • Why interviewers love it: it tests whether you can design what each recursive call communicates.

Order: Diameter → Maximum Path Sum → Longest Univalue Path → LCA II → Smallest Subtree of Deepest Nodes → Max Difference Node–Ancestor.

Longest Univalue Path

Core idea: A "univalue path" is a chain of nodes that all share the same value. The longest one can bend at some node — going down-left and down-right — without touching the root. So at each node, post-order DFS returns the longest single arm you can extend upward to your parent (which the parent can only use if it shares your value), while separately combining your two arms (left + right) to update a global best. Return one arm up; score with both. The catch versus Diameter: an arm only grows across an edge to an equal-valued child — a value change snaps the chain to zero.

Problem, rephrased

Forget the LeetCode phrasing. Here's the scenario:

You have an org chart (a binary tree) where every node carries a team label. A "homogeneous run" is a connected path of people who all belong to the same team. You want the longest such run, measured in edges (the number of hops between people, not the number of people). The run can start anywhere, end anywhere, and bend through a shared manager — it does not have to include the CEO (root).

Formally: given the root of a binary tree, return the length (number of edges) of the longest path where every node on the path has the same value. The path may pass through, or completely avoid, the root.

Consider this small tree:

Tree [5,4,5,1,1,null,5]: longest univalue path is the straight chain of three 5s on the right spine, 2 edges

Path (by values) Edges Same value? Note
5 → 5 → 5 (root, right, right-right) 2 yes (all 5) the answer: a straight chain of three 5s
4 alone 0 yes single node = 0 edges
1 ← 4 → 1 — no the 4 breaks the run; not univalue
5(root) → 4 — no values differ across the edge → not allowed

The longest univalue path here is the three 5s on the right spine: 2 edges. Note we count edges, so a path of n nodes scores n − 1.

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.