Problems/Trees/Maximum Sum of a Continuous Path in a Binary Tree
Trees
hard

Maximum Sum of a Continuous Path in a Binary Tree

Find the maximum sum of any path in a binary tree. This problem tests your understanding of tree traversals and dynamic programming.

treerecursiondynamic programmingdepth-first search

Problem Statement

Given a binary tree where each node has an integer value, determine the path between any two nodes (or a single node) that yields the largest possible sum. The path must form a continuous sequence of parent-child connections in the tree.

Example 1
Input: Tree: Root(1) -> Left(2) -> Left(3), Root(1) -> Right(4) -> Right(5)
Output: 12
The path 2 -> 1 -> 4 -> 5 yields the largest sum: 2 + 1 + 4 + 5 = 12.
Example 2
Input: Tree: Root(-3) -> Left(-10), Root(-3) -> Right(5)
Output: 5
The path consisting of only the node with value 5 yields the largest sum, as including -3 or -10 would decrease the overall sum.
Constraints
  • -The tree can contain positive, negative, and zero values.
  • -The tree contains at least one node.
  • -Node values are integers within a reasonable range (e.g., -1000 to 1000).
  • -The path must be a continuous sequence of nodes connected by edges.

Brute Force Approach

The brute force approach involves examining every possible path within the tree. Think of it like physically tracing every possible route with your finger and calculating the sum for each. This is done by generating all possible paths and then calculating the sum of each path, keeping track of the maximum sum encountered. This approach is very inefficient.

TimeO(n^2)
SpaceO(n)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem