Binary Tree Maximum Path Sum

Try to solve the Binary Tree Maximum Path Sum problem.

We'll cover the following

Statement#

Given the root of a binary tree, return the maximum sum of any non-empty path.

A path in a binary tree is defined as follows:

  • A sequence of nodes in which each pair of adjacent nodes must have an edge connecting them.
    • A node can only be included in a path once at most.
    • Including the root in the path is not compulsory.

You can calculate the path sum by adding up all node values in the path. To solve this problem, calculate the maximum path sum given the root of a binary tree so that there won’t be any greater path than it in the tree.

Constraints:

  • 1≤1\leq Number of nodes in the tree ≤500\leq500.
  • −1000≤-1000 \leq Node.value ≤1000\leq 1000

Examples#

Created with Fabric.js 3.6.6 Input: Level order Maximum path sum is 19+17+5 = 41. 41 -8 2 17 1 4 19 5 Sample example 1 -8 2 17 1 4 19 5 -8 2 17 1 4 19 5

1 of 3

Created with Fabric.js 3.6.6 Input: Level order 7 3 4 -1 -3 14 Maximum path sum is 7+3+4 = 14. 7 3 4 -1 -3 Sample example 2 7 3 4 -1 -3

2 of 3

Created with Fabric.js 3.6.6 Maximum path sum is 6+7+8 = 21. Input: Level order 6 7 8 21 6 7 8 Sample example 3 6 7 8

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Binary Tree Maximum Path Sum

1

What is the maximum path sum for the given binary tree?

   -8   / \  2   17 / \  / \1  4 24  5

level order = [-8, 2, 17, 1, 4, 24, 5]

A)

45

B)

46

C)

47

D)

48

Question 1 of 30 attempted

Figure it out!#

Here’s a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Initialize a maximum sum to negative infinity.

For a leaf node, determine its contribution equal to its value.

Otherwise, determine a node’s contribution as its value plus the greater of the contributions of its left and right children.

Update maximum sum if the above is greater than previous maximum sum.

Try it yourself#

Implement your solution in main.py in the following coding playground.

Python
usercode > main.py
Input #1
%0 node_1 -8 node_2 2 node_1->node_2 node_3 17 node_1->node_3 node_4 1 node_2->node_4 node_5 4 node_2->node_5 node_6 19 node_3->node_6 node_7 5 node_3->node_7
Visualization for Input #1
Binary Tree Maximum Path Sum

Solution: Serialize and Deserialize Binary Tree

Solution: Binary Tree Maximum Path Sum