Maximum path sum
Flipkart
MoodysThe problem
In a binary tree, a path is a list of nodes where there is an edge between every pair of neighbouring nodes. A node may only make a single appearance in the sequence.
The total of each node's values along a path is its path sum. Return the largest path sum of all non-empty paths given the root of a binary tree.
Note: The path does not have to go via the root.
Input : root = [20, 9, -10, null, null, 15, 7] Output : 34 Explanation : The path from node 15 to node 9 has maximum path sum. The path is 15 -> -10 -> 20 -> 9.
**Input : **root = [-10, 9, 20, null, null, 15, 7] Output : 42 Explanation : The path from node 15 to node 7 has maximum path sum. The path is 15 -> 20 -> 7.
Input : root = [1, 2, 3, null, 4]
- 1 <= Number of Nodes <= 3*104
- -103 <= Node.val <= 103
cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int data;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int val) : data(val) , left(nullptr) , right(nullptr) {}
* };
**/
class Solution {
public:
int maxPathSum(TreeNode* root) {
//your code goes here
}
};java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int data;
* TreeNode left;
* TreeNode right;
* TreeNode(int val) { data = val; left = null, right = null }
* }
**/
class Solution {
public int maxPathSum(TreeNode root) {
//your code goes here
}
}python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxPathSum(self, root):
#your code goes herejavascript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null){
* this.data = val;
* this.left = null;
* this.right = null;
* }
* }
**/
class Solution {
maxPathSum(root) {
//your code goes here
}
}csharp
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public int MaxPathSum(TreeNode root) {
//your code goes here
}
}go
// type TreeNode struct {
// Val int
// Left *TreeNode
// Right *TreeNode
// }
func maxPathSum(root *TreeNode) int {
}Stuck? Show a way to structure it+
- 01Return the best single-branch gain that a parent can extend.
- 02Ignore negative child gains by clamping them to zero.
- 03Update a global answer with the node plus both useful child gains.
- 04Return only one downward branch to the parent, never a forked path.
Reference answer
Then expect these follow-ups
How would you reconstruct the maximum path?
Tests: reconstruction
Why may the global candidate use both children?
Tests: tree-path proof
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question