Binary Tree Maximum Path Sum - Video Solutions

Problem Overview: You are given a binary tree where each node contains an integer (positive or negative). A path can start and end at any node, but it must follow parent-child connections. The task is to compute the maximum possible sum of values along any such path.

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

This approach performs a postorder traversal using depth-first search. For every node, compute the maximum gain it can contribute to a path that extends upward to its parent. The key insight: a path passing through a node may include both left and right children, but a parent can only continue one side. During recursion, calculate left_gain = max(dfs(left), 0) and right_gain = max(dfs(right), 0). The candidate maximum path through the node becomes node.val + left_gain + right_gain, which updates a global maximum. The recursive function returns node.val + max(left_gain, right_gain) so the parent continues the best single branch. Every node is visited once, giving O(n) time. The recursion stack uses O(h) space where h is tree height.

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

This approach frames the same idea explicitly as dynamic programming on trees. Each node stores the best downward path sum starting from that node. While traversing the tree (typically postorder), compute two values: the best downward path returned to the parent and the best path passing through the node that may include both children. The recurrence relation is similar: downward = node.val + max(0, left, right). Meanwhile, update a global maximum with node.val + max(0,left) + max(0,right). The DP perspective emphasizes that each node's result depends only on its children’s computed values. Since each node contributes constant work and the traversal touches every node once, the runtime remains O(n) with O(h) auxiliary stack space.

Recommended for interviews: Interviewers typically expect the recursive DFS solution. It shows that you recognize a tree path can branch through a node but only one branch continues upward. Explaining the difference between the "global path" and the "extendable path" demonstrates strong understanding of tree recursion and dynamic programming on trees.