Tree DP primer: post-order with side state

Three chapters back, every recursive helper on a tree returned exactly one thing: a height, a count, a Boolean. The function’s return value carried the answer up the call stack, and the wrapper called the helper at the root and returned the result. Clean. Familiar. The shape every tree problem so far has fit into.

LC 1372 breaks that shape. The function asks for the longest zigzag path in a binary tree, meaning the longest run of nodes that alternates left, right, left, right (or right, left, right, left) without repeating a direction. A reasonable first instinct is to recurse, return “the longest zigzag below this node”, and call it done. That instinct is wrong, and the way it’s wrong is what this chapter is about. The longest zigzag a path can have while passing through this node is not the same number the parent needs to keep its own chain going. Two distinct numbers. One return slot. The recursion has to give the parent what it needs and also record the answer somewhere, and the somewhere is not the return value.

Tree DP is the family of recursions that solves this by splitting the channel. The helper’s return type carries what the parent needs to combine; a closure-captured side state carries the global answer. Three reusable shapes cover almost every problem at LC Easy and Medium that fits the pattern. This chapter teaches all three. Heavier extensions, including handling negative subtrees, encoding state machines on the tree, and the marquee Hard problems like LC 124 Maximum Path Sum and LC 337 House Robber III, wait for Tree DP advanced.

When this pattern fits

Reach for tree DP when a problem hands you a binary tree and asks for an answer that one of the three shapes below can produce. The decision flowchart is short.

flowchart TD
    Q[Tree problem in front of you]
    Q --> Q1{Are you collecting<br/>per-leaf or per-path values?}
    Q1 -- Yes --> S1[Shape 1: accumulator<br/>LC 257 Binary Tree Paths]
    Q1 -- No --> Q2{Are you computing a value<br/>per subtree and aggregating<br/>across them?}
    Q2 -- Yes --> S2[Shape 2: aggregate + side state<br/>LC 508 Most Frequent Subtree Sum]
    Q2 -- No --> Q3{Is the answer the longest<br/>or largest something passing<br/>through some node?}
    Q3 -- Yes --> S3[Shape 3: diameter trick<br/>LC 1372 Longest ZigZag Path]
    Q3 -- No --> ESC[Probably not tree DP, see<br/>traversals or advanced tree DP]

The pattern fails for problems that flip a subtree’s contribution based on signed values (LC 124’s max(0, gain) cutoff), problems that need a state machine attached to each node (LC 337 House Robber III’s (rob, skip) pair, LC 968 Binary Tree Cameras’ three-state DP), and problems where the “tree” is actually a graph with shared descendants. Those belong to other chapters. The three shapes here are deliberately small. Internalize them, and almost every Hard tree-DP problem in interview rotation reads as one of these shapes with a small twist.

The three shapes share one skeleton

Every shape in this chapter is the same post-order helper with three knobs: what the helper returns, what side state the closure captures, and what the helper does at a leaf. The skeleton is one function:

function helper(node):
    if node is null:
        return identity_for_this_problem
    left_result  = helper(node.left)
    right_result = helper(node.right)
    combined = combine(node.val, left_result, right_result)
    side_state.record(combined)         # or do nothing, depending on shape
    return what_parent_needs(combined)

That is the chapter. The three shapes below differ only in identity_for_this_problem, what record does, and what what_parent_needs returns. CLRS Problem 15-6, “Planning a company party”, is the canonical textbook DP-on-tree exercise and fits the same skeleton: the recurrence C[x] = max(sum_children(C), x.conviv + sum_grandchildren(C)) is exactly combine, and the runtime is O(n) because every node is visited once.¹

flowchart TD
    R[node 1<br/>shape 2: subtree sum 18<br/>shape 3: depth 3]
    R --- A[node 2<br/>shape 2: sum 11<br/>shape 3: depth 2]
    R --- B[node 3<br/>shape 2: sum 4<br/>shape 3: depth 1]
    A --- C[node 4<br/>shape 2: sum 4<br/>shape 3: depth 1]
    A --- D[node 5<br/>shape 2: sum 5<br/>shape 3: depth 1]
    C --- E[node 6 LEAF<br/>shape 2: sum 6<br/>shape 3: depth 0]
    D --- F[node 7 LEAF<br/>shape 2: sum 7<br/>shape 3: depth 0]

Shape 1: accumulator on the call stack

The first shape is the simplest. The answer is a collection of per-path items (every root-to-leaf path, every path satisfying some property) and the helper threads the running collection down through a parameter, committing at every leaf. The canonical problem is LC 257 Binary Tree Paths.²

The honest first attempt for LC 257 is brute-force concatenation: at every node, collect the paths from the left subtree, the paths from the right subtree, prepend the current node’s value to each, and return. Correct. Also slow, because every prepend allocates a fresh list, and the total allocation is bounded by the sum of path lengths times the recursion depth, an O(n·h) allocation count with bad constants.

# Brute force: paths are collected and rebuilt at every level
def binary_tree_paths_brute(root):
    if root is None:
        return []
    if root.left is None and root.right is None:
        return [str(root.val)]
    result = []
    for sub in binary_tree_paths_brute(root.left):
        result.append(f"{root.val}->{sub}")
    for sub in binary_tree_paths_brute(root.right):
        result.append(f"{root.val}->{sub}")
    return result

The fix is to flip direction. Pass the running path down through a parameter (a list that grows as we descend and shrinks as we ascend) and write to a closure-captured output list whenever the helper hits a leaf. The append-and-pop pair is what makes the algorithm O(total path length) instead of O(n·h) with allocation overhead per level.

def binary_tree_paths(root):
    out = []
    if root is None:
        return out

    def walk(node, path):
        path.append(str(node.val))
        if node.left is None and node.right is None:
            out.append("->".join(path))
        else:
            if node.left is not None:
                walk(node.left, path)
            if node.right is not None:
                walk(node.right, path)
        path.pop()  # backtrack so siblings see a clean prefix

    walk(root, [])
    return out

# LC 257. Binary Tree Paths
"""LC 257. Return every root-to-leaf path as a list of "->"-joined strings.

Shape 1 of tree DP: accumulator-on-the-stack. The helper threads a running
path down through a parameter and commits to the closure-captured list at
every leaf. Backtracking on the way up keeps siblings independent.
"""
import sys
from dataclasses import dataclass
from typing import List, Optional


# DSH-04: raise the recursion limit once at module top so that deep tree
# inputs (LC 1372 caps at 50,000 nodes; LC 257's worst case is the same
# skewed-chain shape) don't hit CPython's default 1,000-frame ceiling.
sys.setrecursionlimit(10**6)


@dataclass
class TreeNode:
    val: int = 0
    left: Optional["TreeNode"] = None
    right: Optional["TreeNode"] = None


def binary_tree_paths(root: Optional[TreeNode]) -> List[str]:
    out: List[str] = []
    if root is None:
        return out

    def walk(node: TreeNode, path: List[str]) -> None:
        path.append(str(node.val))
        if node.left is None and node.right is None:
            out.append("->".join(path))
        else:
            if node.left is not None:
                walk(node.left, path)
            if node.right is not None:
                walk(node.right, path)
        path.pop()  # backtrack so siblings see a clean prefix

    walk(root, [])
    return out

// LC 257. Binary Tree Paths
import java.util.ArrayList;
import java.util.List;

public final class Sol {

    public static final class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) { this.val = val; }
    }

    // Shape 1 of tree DP: accumulator on the call stack with backtracking.
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> out = new ArrayList<>();
        if (root == null) return out;
        walk(root, new StringBuilder(), out);
        return out;
    }

    private void walk(TreeNode node, StringBuilder path, List<String> out) {
        int len = path.length();
        if (len > 0) path.append("->");
        path.append(node.val);
        if (node.left == null && node.right == null) {
            out.add(path.toString());
        } else {
            if (node.left != null) walk(node.left, path, out);
            if (node.right != null) walk(node.right, path, out);
        }
        path.setLength(len); // backtrack so siblings see a clean prefix
    }
}

// LC 257. Binary Tree Paths
#include <string>
#include <vector>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    explicit TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Shape 1 of tree DP: accumulator on the call stack with backtracking.
    std::vector<std::string> binaryTreePaths(TreeNode* root) {
        std::vector<std::string> out;
        if (root == nullptr) return out;
        std::string path;
        walk(root, path, out);
        return out;
    }

private:
    void walk(TreeNode* node, std::string& path, std::vector<std::string>& out) {
        std::size_t saved = path.size();
        if (!path.empty()) path += "->";
        path += std::to_string(node->val);
        if (node->left == nullptr && node->right == nullptr) {
            out.push_back(path);
        } else {
            if (node->left != nullptr) walk(node->left, path, out);
            if (node->right != nullptr) walk(node->right, path, out);
        }
        path.resize(saved); // backtrack so siblings see a clean prefix
    }
};

// LC 257. Binary Tree Paths
package main

import "strconv"

// TreeNode is the canonical LeetCode binary-tree shape.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// Shape 1 of tree DP: accumulator on the call stack. Go's immutable strings
// make backtracking implicit: each recursive call rebinds its own `path`
// local, so siblings naturally see a clean prefix.
func binaryTreePaths(root *TreeNode) []string {
	out := []string{}
	if root == nil {
		return out
	}
	var walk func(node *TreeNode, path string)
	walk = func(node *TreeNode, path string) {
		if path == "" {
			path = strconv.Itoa(node.Val)
		} else {
			path = path + "->" + strconv.Itoa(node.Val)
		}
		if node.Left == nil && node.Right == nil {
			out = append(out, path)
			return
		}
		if node.Left != nil {
			walk(node.Left, path)
		}
		if node.Right != nil {
			walk(node.Right, path)
		}
	}
	walk(root, "")
	return out
}

The path.pop() line is load-bearing. Forget it and the right sibling sees the left sibling’s path appended to its own, producing strings like "1->2->4->5" for what should be "1->3->5". The pattern is the same in every language: Java’s StringBuilder.setLength(saved), C++‘s path.resize(saved), Go’s path rebound by value at every recursive call. Pick one strategy per language and stick with it.

Shape 2: post-order returns aggregate, side state accumulates

The second shape is the one this chapter spends the most time on. The answer is a per-subtree aggregate (every subtree’s sum, every subtree’s size, the most-frequent subtree sum across the whole tree) and the helper does two things at every node: it returns the aggregate the parent will combine, and it records that aggregate in a closure-captured collection. The canonical problem is LC 508 Most Frequent Subtree Sum.

LC 508 asks: given the root of a binary tree, return every subtree sum that appears the most often. Sample: the tree [5, 2, -3] produces three subtree sums (2 from the left leaf, -3 from the right leaf, and 4 from the whole tree, summing 5 + 2 + -3), each appearing exactly once. Tie. The answer is [2, -3, 4] in any order. The tree [5, 2, -5] produces sums 2, -5, and 2 (because 5 + 2 + -5 = 2), so the mode is 2 with frequency 2 and the answer is [2].

The recurrence writes itself. The sum of a subtree rooted at node is node.val + sum(node.left) + sum(node.right), with the empty tree contributing 0. That’s combine. What’s new is record: every time the helper computes a subtree sum, it bumps a hash counter keyed on that sum. The mode of the counter at the end of the recursion is the answer.

def find_frequent_tree_sum(root):
    if root is None:
        return []
    counts = Counter()

    def subtree_sum(node):
        if node is None:
            return 0
        s = node.val + subtree_sum(node.left) + subtree_sum(node.right)
        counts[s] += 1
        return s

    subtree_sum(root)
    best = max(counts.values())
    return [s for s, c in counts.items() if c == best]

# LC 508. Most Frequent Subtree Sum
"""LC 508. Return every subtree sum that ties for the highest frequency.

Shape 2 of tree DP: post-order returns aggregate, side accumulator records
every value the helper produces. The helper's return is what the parent
needs (the subtree sum); the answer lives in a separate channel (a Counter
keyed on every sum the recursion has ever produced).
"""
import sys
from collections import Counter
from dataclasses import dataclass
from typing import List, Optional


sys.setrecursionlimit(10**6)


@dataclass
class TreeNode:
    val: int = 0
    left: Optional["TreeNode"] = None
    right: Optional["TreeNode"] = None


def find_frequent_tree_sum(root: Optional[TreeNode]) -> List[int]:
    if root is None:
        return []

    counts: Counter[int] = Counter()

    def subtree_sum(node: Optional[TreeNode]) -> int:
        if node is None:
            return 0
        s = node.val + subtree_sum(node.left) + subtree_sum(node.right)
        counts[s] += 1
        return s

    subtree_sum(root)
    best = max(counts.values())
    return [s for s, c in counts.items() if c == best]

// LC 508. Most Frequent Subtree Sum
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public final class Sol {

    public static final class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) { this.val = val; }
    }

    // Shape 2 of tree DP: post-order returns the subtree sum; a side
    // accumulator (the counts map) records every sum we produce. The
    // single-element int[] best is the canonical Java idiom for mutating
    // a primitive from inside a recursive helper without a class field.
    public int[] findFrequentTreeSum(TreeNode root) {
        if (root == null) return new int[0];
        Map<Integer, Integer> counts = new HashMap<>();
        int[] best = new int[]{0};
        subtreeSum(root, counts, best);
        List<Integer> modes = new ArrayList<>();
        for (Map.Entry<Integer, Integer> e : counts.entrySet()) {
            if (e.getValue() == best[0]) modes.add(e.getKey());
        }
        int[] res = new int[modes.size()];
        for (int i = 0; i < modes.size(); i++) res[i] = modes.get(i);
        return res;
    }

    private int subtreeSum(TreeNode node, Map<Integer, Integer> counts, int[] best) {
        if (node == null) return 0;
        int s = node.val
              + subtreeSum(node.left, counts, best)
              + subtreeSum(node.right, counts, best);
        int c = counts.getOrDefault(s, 0) + 1;
        counts.put(s, c);
        if (c > best[0]) best[0] = c;
        return s;
    }
}

// LC 508. Most Frequent Subtree Sum
#include <unordered_map>
#include <vector>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    explicit TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Shape 2 of tree DP: post-order returns subtree sum; counts side
    // accumulator records every sum. C++'s int& best parameter is the
    // pass-by-reference equivalent of Java's int[] best wrapper.
    std::vector<int> findFrequentTreeSum(TreeNode* root) {
        std::vector<int> res;
        if (root == nullptr) return res;
        std::unordered_map<int, int> counts;
        int best = 0;
        subtreeSum(root, counts, best);
        for (const auto& kv : counts) {
            if (kv.second == best) res.push_back(kv.first);
        }
        return res;
    }

private:
    int subtreeSum(TreeNode* node, std::unordered_map<int, int>& counts, int& best) {
        if (node == nullptr) return 0;
        int s = node->val
              + subtreeSum(node->left, counts, best)
              + subtreeSum(node->right, counts, best);
        int c = ++counts[s];
        if (c > best) best = c;
        return s;
    }
};

// LC 508. Most Frequent Subtree Sum
package main

// Shape 2 of tree DP: post-order returns subtree sum; counts map captures
// every sum the recursion produces. Go's closure over `counts` and `best`
// is the natural idiom: no array wrapper, no class field.
func findFrequentTreeSum(root *TreeNode) []int {
	if root == nil {
		return []int{}
	}
	counts := map[int]int{}
	best := 0
	var subtreeSum func(node *TreeNode) int
	subtreeSum = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		s := node.Val + subtreeSum(node.Left) + subtreeSum(node.Right)
		counts[s]++
		if counts[s] > best {
			best = counts[s]
		}
		return s
	}
	subtreeSum(root)
	res := []int{}
	for s, c := range counts {
		if c == best {
			res = append(res, s)
		}
	}
	return res
}

The reason this is tree DP and not just a recursion is the second channel. The helper’s return value (s) is what its parent will use to compute its own subtree sum. The hash counter (counts) is where the answer to the original question lives. The two channels are independent. The wrapper at the bottom of the function never reads subtree_sum(root); it reads counts. That separation is the chapter’s central move, and it’s the one that confuses readers coming from chapters where every recursive helper had a single return slot.

The combine step here is associative (addition), so the order of recursion doesn’t matter and the analysis is clean. Each node is visited once, does O(1) work plus an amortized-O(1) hash insert, so total time is O(n).³ Space is O(n) for the counter (every subtree sum could be distinct in the worst case) plus O(h) for the recursion stack.

Shape 3: the diameter trick

The third shape is the one named in the chapter’s opening. The answer is “the longest or largest something passing through some node”, where the something extends downward from any node, possibly turning at that node and continuing into the other subtree. The helper returns a per-subtree downward measure (a depth, a chain length); a closure-captured global takes the max with the through-this-node composite at every step. The classic example is LC 543 Diameter of Binary Tree, which the Binary tree fundamentals chapter introduced as a stretch problem.¹ LC 1372 Longest ZigZag Path is the same shape with one extra wrinkle.

LC 1372 asks for the longest zigzag path. A zigzag is a sequence of nodes where each step alternates direction (left, then right, then left, then right). The length is the number of nodes minus one, so a single node has length 0. Sample: on [1, null, 1, 1, 1, null, null, 1, 1, null, 1], the answer is 3 (a four-node path going right, left, right).

The instinct that fails here is the same one that fails on LC 543: recurse, return “the longest zigzag below this node”, and read that off the root. That number is wrong because the longest zigzag might pass through some internal node, with one half going down-left and the other half going down-right, and the wrapper at the root would never see it.

The diameter trick fixes the instinct in one move. Have the helper return the chain length the parent needs to keep its own zigzag going. At the same time, at every node the helper visits, update a closure-captured global with the longest zigzag passing through this node. Two channels. The helper’s return is the parent’s input; the global is the answer. There is one subtlety unique to LC 1372: a zigzag has direction. After visiting a node going leftward, the next step must go rightward; after visiting a node going rightward, the next step must go leftward. So the helper has to return two numbers, one for each entry direction.

def longest_zig_zag(root):
    best = 0

    def helper(node):
        nonlocal best
        if node is None:
            return (-1, -1)
        _, left_right = helper(node.left)
        right_left, _ = helper(node.right)
        left_len  = left_right + 1   # zigzag entering me leftward, then turning right
        right_len = right_left + 1   # zigzag entering me rightward, then turning left
        local_best = left_len if left_len > right_len else right_len
        if local_best > best:
            best = local_best
        return (left_len, right_len)

    helper(root)
    return best

# LC 1372. Longest ZigZag Path in a Binary Tree
"""LC 1372. Return the longest zigzag path length in a binary tree.

Shape 3 of tree DP (the diameter trick), composed with shape 4 (tuple
return). The helper returns a 2-tuple (left_extending, right_extending)
describing how far a zigzag chain entering this node from above can extend
in each direction. A closure-captured global takes the max with the
through-this-node composite at every step. The final answer lives in the
global, NOT in the helper's return value: that split is the chapter's
load-bearing insight.
"""
import sys
from dataclasses import dataclass
from typing import Optional, Tuple


sys.setrecursionlimit(10**6)


@dataclass
class TreeNode:
    val: int = 0
    left: Optional["TreeNode"] = None
    right: Optional["TreeNode"] = None


def longest_zig_zag(root: Optional[TreeNode]) -> int:
    if root is None:
        return 0

    best = 0

    def helper(node: Optional[TreeNode]) -> Tuple[int, int]:
        nonlocal best
        if node is None:
            return (-1, -1)  # sentinel: no chain to extend
        # Each child contributes the chain ending in the OTHER direction:
        # entering me leftward continues the parent's right-extending chain.
        _, left_right = helper(node.left)
        right_left, _ = helper(node.right)
        left_len = left_right + 1
        right_len = right_left + 1
        # Update the global BEFORE building the return tuple, so the
        # left-to-right argument evaluation order in max can never see
        # stale state (see §"Two pitfalls that bite", side-effect ordering).
        local_best = left_len if left_len > right_len else right_len
        if local_best > best:
            best = local_best
        return (left_len, right_len)

    helper(root)
    return best

// LC 1372. Longest ZigZag Path in a Binary Tree
public final class Sol {

    public static final class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) { this.val = val; }
    }

    // Shape 3 of tree DP (diameter trick) + shape 4 (tuple return).
    // int[2] {leftExtending, rightExtending} is the canonical Java
    // idiom for tuple returns; -1 in both slots is the null sentinel.
    public int longestZigZag(TreeNode root) {
        if (root == null) return 0;
        int[] best = new int[]{0};
        helper(root, best);
        return best[0];
    }

    private int[] helper(TreeNode node, int[] best) {
        if (node == null) return new int[]{-1, -1};
        int[] leftPair  = helper(node.left, best);
        int[] rightPair = helper(node.right, best);
        // Each child contributes the chain ending in the OTHER direction.
        int leftLen  = leftPair[1] + 1;
        int rightLen = rightPair[0] + 1;
        int localBest = leftLen > rightLen ? leftLen : rightLen;
        if (localBest > best[0]) best[0] = localBest;
        return new int[]{leftLen, rightLen};
    }
}

// LC 1372. Longest ZigZag Path in a Binary Tree
#include <utility>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    explicit TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Shape 3 of tree DP (diameter trick) + shape 4 (tuple return).
    // std::pair<int,int> {leftExtending, rightExtending}; pass-by-ref
    // best is the natural C++ idiom for the closure-captured global.
    int longestZigZag(TreeNode* root) {
        if (root == nullptr) return 0;
        int best = 0;
        helper(root, best);
        return best;
    }

private:
    std::pair<int, int> helper(TreeNode* node, int& best) {
        if (node == nullptr) return {-1, -1};
        auto leftPair  = helper(node->left, best);
        auto rightPair = helper(node->right, best);
        // Each child contributes the chain ending in the OTHER direction.
        int leftLen  = leftPair.second + 1;
        int rightLen = rightPair.first + 1;
        int localBest = leftLen > rightLen ? leftLen : rightLen;
        if (localBest > best) best = localBest;
        return {leftLen, rightLen};
    }
};

// LC 1372. Longest ZigZag Path in a Binary Tree
package main

// Shape 3 of tree DP (diameter trick) + shape 4 (tuple return).
// Go closure over `best` is the natural idiom; a 2-int slice carries the
// (leftExtending, rightExtending) tuple back up the recursion.
func longestZigZag(root *TreeNode) int {
	if root == nil {
		return 0
	}
	best := 0
	var helper func(node *TreeNode) (int, int)
	helper = func(node *TreeNode) (int, int) {
		if node == nil {
			return -1, -1 // sentinel: no chain to extend
		}
		_, leftRight := helper(node.Left)
		rightLeft, _ := helper(node.Right)
		// Each child contributes the chain ending in the OTHER direction.
		leftLen := leftRight + 1
		rightLen := rightLeft + 1
		localBest := leftLen
		if rightLen > localBest {
			localBest = rightLen
		}
		if localBest > best {
			best = localBest
		}
		return leftLen, rightLen
	}
	helper(root)
	return best
}

Three details earn their place. First, the null sentinel (-1, -1). Adding 1 to it gives 0, which is the correct chain length for a leaf (a single node, no edges traversed). Second, the helper takes the opposite direction’s chain from each child: the left child contributes left_right, the chain that ended going right (because to enter me leftward, you came down from a parent on my left and continued into my left subtree, where the next step had to go right). The right child contributes right_left for the symmetric reason. Third, the global update happens at every node, leaves included. Skipping the leaf update is harmless on this problem because leaves contribute 0 to best, but it is a habit worth keeping; on adjacent problems, the leaf update is what catches the answer.

This chapter’s most cited bug also lives on LC 1372. A reader, having seen the diameter pattern, writes the “obvious” line self.longest = max(self.longest, 1 + self.helper(node.left)[1]). Looks fine. Returns 1 instead of 2 on the sample input [1, 1, null, 1, null, 1, null, null, 1]. The reason is Python’s argument evaluation order: max(a, b) reads a first, then evaluates b, then compares. The recursive call buried in b mutates self.longest. But self.longest was already read into the temporary holding a before the mutation ran, so max operates on stale data.²

What it actually costs

Variable definitions: n is the number of nodes; h is the height (O(log n) for balanced trees, n - 1 for skewed).³ The shape-1 cost is worth a sentence of explanation. Many editorials report LC 257 as O(n), which under-counts the per-leaf string render. With up to O(n) leaves and each path up to h characters, the rendering cost alone is O(n·h) worst case, collapsing to O(n log n) on balanced inputs. The balanced-tree number is what readers will see in practice.

The recursion-stack space deserves an extra note. CPython’s default limit is 1,000 frames. LC 1372 caps at 50,000 nodes, and a worst-case skewed input recurses 50,000 levels deep. The Python reference raises the limit at module top-level with sys.setrecursionlimit(10**6).⁴ Java, C++, and Go have larger default stacks (1 MB or more on most platforms), but the same skewed-input case still risks a stack overflow on adversarial test data. The int[] best, int& best, and closure-captured best idioms in the four reference implementations work around the same problem from a different angle: they keep the global out of class fields (Python: out of self) so the helper closes over a single mutable cell with no per-frame overhead.

Two pitfalls that bite

A third trap is more subtle: assuming “the tree” can be any graph. The three shapes here rely on each subtree being independent of every other subtree, which holds for trees and breaks immediately on a graph with shared descendants or a cycle. If the input has either, the chapter you want is in Part 8 Graphs, not this one.

Problem ladder

CORE (solve all three to claim chapter mastery)

• LC 257: Binary Tree Paths [Easy] • shape 1 accumulator
• LC 508: Most Frequent Subtree Sum [Medium] • shape 2 aggregate + side state
• LC 1372: Longest ZigZag Path in a Binary Tree [Medium] • shape 3 diameter trick + tuple return ★

STRETCH (optional)

• LC 250: Count Univalue Subtrees [Medium] • shape 2 with a (is_univalue, value) tuple return (LeetCode Premium; LC 508 in CORE is the free shape-2 problem)

The CORE three exercise all three shapes once each. The chapter’s signature problem (★) is LC 1372: the tuple return composes shape 3 (diameter trick) with the multi-piece return that shapes 2 and 3 both bend toward, and the side-effect-ordering pitfall is rooted on this exact problem. LC 543 Diameter of Binary Tree, the simpler diameter-trick exemplar, is owned by Binary tree fundamentals as a stretch problem; readers who solved it there will recognize LC 1372 as the same shape with one direction-tracking twist on top.

The ladder spans Easy and Medium and stops there. The Hard tree-DP problems readers tend to ask about (LC 124 Maximum Path Sum, LC 337 House Robber III, LC 968 Binary Tree Cameras) all extend these three shapes with signed-value handling, state-machine returns, or both. Those live in Tree DP advanced and are deliberately out of scope here. The chapter that owns them is the right place to learn the max(0, gain) cutoff, the (rob, skip) two-state return, and the three-state camera DP.

Where this leads

The natural next step is Tree DP advanced. Three of its problems are direct extensions of what this chapter taught: LC 124 Maximum Path Sum is shape 3 plus the max(0, child_gain) cutoff that handles negative subtrees; LC 337 House Robber III is shape 2 with a (rob_this, skip_this) 2-tuple return; LC 968 Binary Tree Cameras is shape 2 with a three-state return. The reader who has internalized the three shapes here will recognize each of those as one shape plus a small twist, and the recurrence will draft itself.

Closer at hand, BSTs uses a very similar two-channel pattern for in-order validation: a helper returns the subtree’s (is_bst, min, max) tuple while a global accumulates whether the whole tree is a BST. Same skeleton, different combine step. And Tries uses the post-order template for a different purpose entirely (building a structural representation of a string set), but the muscle memory of “recurse into children, combine post-order” is what makes the chapter feel familiar instead of new.

References