Max Path Sum In Binary Tree

Tags

Max Path Sum In Binary Tree

Category

Binary Trees

Difficulty

Hard

Problem Statement

Given a binary tree where each node contains an integer value (which may be negative), find the maximum path sum. A path is defined as any sequence of connected nodes where each node appears at most once. The path does not need to pass through the root, and it can start and end at any node in the tree. The path must contain at least one node.

Intuition

At every node, we have a choice: the maximum path through this node could either (a) continue upward to the parent (as a branch), or (b) form a complete path that goes through this node as the "turning point" (left child -> node -> right child). We track two values at each node: the maximum branch sum (which can be extended by the parent) and the maximum path sum seen so far (which might use both children and thus cannot be extended further).

Approach

  1. Define a recursive function that returns the maximum branch sum (single-direction path) starting from the current node.
  2. At each node, recursively compute the max branch sum from the left and right children.
  3. The max branch sum through the current node is node.value + max(leftBranch, rightBranch), but we also consider just node.value alone (if both children contribute negative sums).
  4. The max path sum through the current node as a turning point is node.value + leftBranch + rightBranch (using both branches).
  5. Update a running maximum with the greatest of: the current node alone, the node plus left branch, the node plus right branch, or the node plus both branches.
  6. Return the branch sum (not the full path sum) to the parent, since only a single-direction path can be extended.

Pseudocode

function maxPathSum(tree):
    maxSum = -infinity
    findMaxSum(tree, maxSum)
    return maxSum

function findMaxSum(node, maxSum):
    if node is null:
        return 0

    leftBranch = max(0, findMaxSum(node.left, maxSum))
    rightBranch = max(0, findMaxSum(node.right, maxSum))

    localMax = node.value + leftBranch + rightBranch
    maxSum = max(maxSum, localMax)

    return node.value + max(leftBranch, rightBranch)

Time & Space Complexity

  • Time: O(n) where n is the number of nodes. Each node is visited exactly once.
  • Space: O(h) where h is the height of the tree, due to the recursion stack. O(log n) for a balanced tree, O(n) for a skewed tree.

Key Insights

  • Clamping child branch sums to 0 with max(0, childBranch) elegantly handles negative subtrees — we simply do not include them.
  • The critical distinction is between a "branch" (extendable by parent) and a "path" (complete, using both sides). Only branches are returned up; paths update the global maximum.
  • The answer might be a single node if all other values are negative.
  • This is a classic post-order traversal pattern: process children before the current node.

Edge Cases

  • A tree with all negative values — the answer is the single node with the largest (least negative) value.
  • A tree with a single node — the answer is that node's value.
  • A perfectly balanced tree — the optimal path might span the full diameter.
  • A skewed tree (essentially a linked list) — the path is a contiguous subarray, reducing to Kadane's algorithm.
  • Nodes with value zero — including them does not increase the sum but extends the path, which is fine.

Linked mentions