Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in C++

Binary Tree Maximum Path Sum

Explore how to calculate the maximum path sum in a binary tree by identifying valid node paths and using depth-first search techniques. Learn to implement this in C++ while considering constraints and path rules to prepare effectively for coding interviews.

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

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

1 / 3

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.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4

Try it yourself

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

C++
usercode > main.cpp
// Definiton of a binary tree node class

// class TreeNode<T> {

//     T data;

//     TreeNode<T> left;

//     TreeNode<T> right;



//     TreeNode(T data) {

//         this.data = data;

//         this.left = null;

//         this.right = null;

//     }

// }



int MaxPathSum(TreeNode<int>* root){



    // Replace this placeholder return statement with your code

    return -1;

}
Binary Tree Maximum Path Sum