Skip to content

Pair Return Pattern

The Pattern That Solves 30% of Tree Interviews

This is the single most important lesson in this course. If you internalize one pattern from all of tree algorithms, make it this one.

The idea is simple: sometimes the answer you're computing is different from the value you need to return to your parent. When that happens, you return one thing and track the other on the side.

That's the pair-return. You'll see it in diameter, max path sum, longest univalue path, and a dozen other problems. Once you recognize the split between "what I track" and "what I return," these problems collapse into the same template.

Problem 1: Diameter of Binary Tree (LC 543)

Problem: Given a binary tree, find the length of the diameter — the longest path between any two nodes. The path does not need to pass through the root. Length is measured in number of edges.

        1
       / \
      2   3
     / \
    4   5

The diameter here is 3: the path 4 → 2 → 1 → 3 (or 5 → 2 → 1 → 3).

The Trap

Your first thought might be: the longest path passes through the root, so just compute the height of the left subtree plus the height of the right subtree.

That works for this example. But consider:

        1
       /
      2
     / \
    4   5
   /     \
  6       7

The longest path is 6 → 4 → 2 → 5 → 7, which has 4 edges. This path passes through node 2, not the root. If you only checked the root, you'd get height(left) + height(right) = 4 + 0 = 4 — that happens to be correct here, but only by coincidence. The path through the root is 1's left height + 1's right height = 4 + 0 = 4. The path through node 2 is 2 + 2 = 4.

In general, the diameter might pass through any internal node. You need to check every node.

Why Brute Force Fails

You could compute, for every node, the height of its left subtree plus the height of its right subtree. Take the maximum. But height computation is \(O(n)\) per node, and there are \(n\) nodes. That's \(O(n^2)\).

The Fix: Return Height, Track Diameter

Here's the insight that makes this \(O(n)\):

At every node, you need two things:

  1. The path through this node = leftHeight + rightHeight. This is a candidate for the diameter.
  2. The height to return to the parent = \(1 + \max(\text{leftHeight}, \text{rightHeight})\). The parent needs this to compute ITS path.

These are different values. The path through a node uses BOTH children. The height to return uses only the TALLER child.

The pair-return: you RETURN the height (for your parent's computation) while TRACKING the diameter (the global answer) on the side.

At each node, height flows upward as the return value while diameter is tracked as a global maximum

int maxDiameter = 0;

int computeHeight(TreeNode* root) {
    if (!root) return 0;
    int leftHeight = computeHeight(root->left);
    int rightHeight = computeHeight(root->right);
    maxDiameter = max(maxDiameter, leftHeight + rightHeight);
    return 1 + max(leftHeight, rightHeight);
}

int diameterOfBinaryTree(TreeNode* root) {
    maxDiameter = 0;
    computeHeight(root);
    return maxDiameter;
}

Notice: the function returns height. It never returns the diameter directly. The diameter is accumulated in maxDiameter as a side effect of computing height.

Trace

        1
       / \
      2   3
     / \
    4   5
Call Node leftHeight rightHeight Path through node maxDiameter after Returns
computeHeight(4) 4 0 0 0 0 1
computeHeight(5) 5 0 0 0 0 1
computeHeight(2) 2 1 (from 4) 1 (from 5) 2 2 2
computeHeight(3) 3 0 0 0 2 1
computeHeight(1) 1 2 (from 2) 1 (from 3) 3 3 3

The path through node 1 is \(2 + 1 = 3\) edges. This is the max across all nodes. The diameter is 3.

Manual check: the longest path is 4 → 2 → 1 → 3, which has 3 edges. Correct.

Problem 2: Binary Tree Maximum Path Sum (LC 124)

Problem: Given a binary tree where each node contains an integer (possibly negative), find the maximum path sum. A path is any sequence of connected nodes where each node appears at most once. The path can start and end at any node.

       -10
       /  \
      9    20
          /  \
         15   7

The max path sum is \(15 + 20 + 7 = 42\). The path goes 15 → 20 → 7, not through the root (because \(-10\) would reduce the sum).

Same Pattern, Harder Decisions

This is the exact same structure as diameter, with one twist: nodes can be negative, so sometimes you don't want to include a subtree at all.

At every node, the path through it can use: - Left branch + this node + right branch (the "arch" path) - Just left branch + this node - Just right branch + this node - Just this node alone (both branches are negative)

The path sum through this node is: \(\text{root.val} + \max(0, \text{leftGain}) + \max(0, \text{rightGain})\).

The \(\max(0, \ldots)\) is how you "prune" a negative subtree. If the left subtree's best contribution is negative, don't include it — take 0 instead.

But what do you RETURN to the parent? The parent can only use a single branch — not both. A path can't fork. So you return: \(\text{root.val} + \max(0, \max(\text{leftGain}, \text{rightGain}))\).

Same split: the answer at this node (arch path using both sides) is different from what you return (single branch for the parent). Track the answer. Return the branch.

int maxPathTotal;

int computeMaxGain(TreeNode* root) {
    if (!root) return 0;

    int leftGain = max(0, computeMaxGain(root->left));
    int rightGain = max(0, computeMaxGain(root->right));

    int pathThroughNode = root->val + leftGain + rightGain;
    maxPathTotal = max(maxPathTotal, pathThroughNode);

    return root->val + max(leftGain, rightGain);
}

int maxPathSum(TreeNode* root) {
    maxPathTotal = -1e9;
    computeMaxGain(root);
    return maxPathTotal;
}

Trace

       -10
       /  \
      9    20
          /  \
         15   7
Call Node leftGain rightGain Path through maxPathTotal Returns
computeMaxGain(9) 9 0 0 9 9 9
computeMaxGain(15) 15 0 0 15 15 15
computeMaxGain(7) 7 0 0 7 15 7
computeMaxGain(20) 20 15 7 42 42 35
computeMaxGain(-10) -10 0 (9 from left, but let's recalculate) 35 25 42 25

Wait — let me redo this carefully. The calls happen depth-first left, then right.

Call Node leftGain rightGain Path through maxPathTotal Returns
computeMaxGain(9) 9 0 0 \(9 + 0 + 0 = 9\) 9 \(9 + 0 = 9\)
computeMaxGain(15) 15 0 0 \(15 + 0 + 0 = 15\) 15 \(15 + 0 = 15\)
computeMaxGain(7) 7 0 0 \(7 + 0 + 0 = 7\) 15 \(7 + 0 = 7\)
computeMaxGain(20) 20 15 7 \(20 + 15 + 7 = 42\) 42 \(20 + 15 = 35\)
computeMaxGain(-10) -10 \(\max(0, 9) = 9\) \(\max(0, 35) = 35\) \(-10 + 9 + 35 = 34\) 42 \(-10 + 35 = 25\)

Node 20 finds the arch path \(15 + 20 + 7 = 42\) and updates maxPathTotal. Node \(-10\) finds a path of 34 through itself, which doesn't beat 42. The final answer is 42.

Notice the key difference between what node 20 uses (both children: 15 and 7) and what it returns (only the better child: \(20 + 15 = 35\)). That's the pair-return in action.

Complexity: \(O(n)\) time, \(O(h)\) space.

The Generalization

When do you need pair-return? Whenever these two conditions hold:

  1. The answer at a node combines both children. Diameter uses leftHeight + rightHeight. Max path sum uses leftGain + rightGain + nodeVal. The combination creates something that uses both branches.

  2. The return value for the parent uses only one branch. Height returns \(1 + \max(\text{left}, \text{right})\). Max gain returns \(\text{nodeVal} + \max(\text{left}, \text{right})\). The parent can only extend through one side.

If the answer COMBINES both children but the return value PICKS one, you need pair-return. Return the pick. Track the combination.

When these two values are the same — when the answer IS the return value — you don't need pair-return. That's the simpler "pure postorder" pattern, which you'll see in the next lesson.

Pair-Return Without a Global Variable

In the code above, we used a global maxDiameter / maxPathTotal. That works, but some people prefer passing a reference:

int computeHeight(TreeNode* root, int& maxDiameter) {
    if (!root) return 0;
    int leftHeight = computeHeight(root->left, maxDiameter);
    int rightHeight = computeHeight(root->right, maxDiameter);
    maxDiameter = max(maxDiameter, leftHeight + rightHeight);
    return 1 + max(leftHeight, rightHeight);
}

int diameterOfBinaryTree(TreeNode* root) {
    int maxDiameter = 0;
    computeHeight(root, maxDiameter);
    return maxDiameter;
}

Same logic, no global state. Either approach is fine in an interview.

Try It

The starter code has diameterOfBinaryTree with a TODO. Implement it using the pair-return pattern.

Input: (the tree built in main)
Output: 3

Predict before running: What is the diameter of a single-node tree? A tree with only a root and one left child?

Challenge: Solve Max Path Sum (LC 124). The key subtlety: when do you clamp a child's contribution to 0? Why can't you just take the max of left and right without clamping?

Challenge 2: Solve Longest Univalue Path (LC 687). Same pair-return structure — but the "height" you return only counts nodes matching the parent's value. Think about what changes in the combine step.

Edge Cases to Watch For

  • All negative values in max path sum: Every node is negative. The answer is the single node with the largest (least negative) value. The max(0, ...) clamping correctly excludes children, leaving just the node value as a candidate.
  • Max path sum: forgetting to clamp to zero: If you return root->val + max(leftGain, rightGain) without clamping, a deeply negative subtree pollutes the parent's gain. Always clamp: max(0, childGain).
  • Global variable not reset: If you call diameterOfBinaryTree on multiple trees without resetting maxDiameter to 0, the result from a previous call leaks into the next. Always reset at the start of the wrapper function.

Problems

Problem Link Difficulty
LC 543 — Diameter of Binary Tree leetcode.com/problems/diameter-of-binary-tree Easy
LC 124 — Binary Tree Maximum Path Sum leetcode.com/problems/binary-tree-maximum-path-sum Hard
LC 687 — Longest Univalue Path leetcode.com/problems/longest-univalue-path Medium