Binary Tree Maximum Path Sum - Video Solutions

Problem Overview: Given a binary tree, compute the maximum sum of any path. A path can start and end at any node, but it must follow parent-child connections. The path does not need to pass through the root.

Approach 1: Recursive Depth-First Search (O(n) time, O(h) space)

This approach performs a post-order traversal using depth-first search. For every node, compute the maximum contribution it can send to its parent. That contribution is node.val + max(leftGain, rightGain), where negative gains are treated as zero. At each node, also evaluate a candidate path that passes through the node using leftGain + node.val + rightGain and update a global maximum. Each node is processed once, giving O(n) time complexity and O(h) recursion stack space where h is tree height. This approach works well because it separates two ideas: the best downward path contribution and the best full path passing through a node.

Approach 2: Dynamic Programming with Tree Traversal (O(n) time, O(h) space)

This method frames the same traversal as a dynamic programming problem on a binary tree. Each node stores the best downward path sum that can extend to its parent. During traversal, compute two values: the best downward extension and the best path passing through the current node using both children. The DP transition is straightforward: ignore negative child paths, update the global maximum with the combined path, and return the best single-branch extension upward. The algorithm still visits each node exactly once, so time complexity remains O(n), with recursion stack space O(h).

Recommended for interviews: The recursive DFS solution is what most interviewers expect. It clearly demonstrates understanding of tree traversal and how to maintain global state during recursion. Explaining why negative child sums are ignored and how the "split path" is evaluated at each node shows strong problem-solving depth.