Maximum Path Sum in a Binary Tree
Last Updated :
03 Feb, 2025
Given a binary tree, the task is to find the maximum path sum. The path may start and end at any node in the tree.
Example:
Input:
Output: 42
Explanation: Max path sum is represented using green colour nodes in the above binary tree.
Input:
Output: 31
Explanation: Max path sum is represented using green colour nodes in the above binary tree.
Approach:
If the maximum sum path in a binary tree passes through the root, there are four possible cases to consider:
- The path consists only the root itself, without involving any children.
- The path starts at the root and extends downward through its right child, possibly continuing to the bottom of the right subtree.
- The path starts at the root and extends downward through its left child, possibly continuing the bottom of the left subtree.
- The path includes the root and spans both the left and right children.
The idea is to keep track of all four paths for each subtree of the tree and pick up the max one in the end.
Implementation:
For each subtree, we want to find the maximum path sum that starts at its root and goes down through either its left or right child. To do this, we create a recursive function (lets say MPS(current root)) that calculates and returns the maximum path sum starting from the root and extending downward through one of its children.
Within the same function, we can also calculate the maximum path sum for the current subtree and compare it with the final answer. This is done by combining the MPS(current root -> left) and MPS(current root -> right) with the value of the current root.
Note that if the MPS() from the left or right child is negative, we simply ignore it while calculating the maximum path sum for the current subtree.
C++
//Driver Code Starts{
// C++ program to find maximum path sum in Binary Tree
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
// Constructor to initialize a new node
Node(int value) {
data = value;
left = nullptr;
right = nullptr;
}
};
//Driver Code Ends }
// Returns the maximum path sum in the subtree with the current node as an endpoint.
// Also updates 'res' with the maximum path sum.
int maxPathSumUtil(Node* root, int& res) {
// Base case: return 0 for a null node
if (root == NULL)
return 0;
// Calculate maximum path sums for left and right subtrees
int l = max(0, maxPathSumUtil(root->left, res));
int r = max(0, maxPathSumUtil(root->right, res));
// Update 'res' with the maximum path sum passing through the current node
res = max(res, l + r + root->data);
// Return the maximum path sum rooted at this node
return root->data + max(l, r);
}
// Returns maximum path sum in tree with given root
int maxPathSum(Node* root) {
int res = root->data;
// Compute maximum path sum and store it in 'res'
maxPathSumUtil(root, res);
return res;
}
//Driver Code Starts{
int main() {
// Representation of input binary tree:
// 10
// / \
// 2 10
// / \ \
// 20 1 -25
// / \
// 3 4
Node* root = new Node(10);
root->left = new Node(2);
root->right = new Node(10);
root->left->left = new Node(20);
root->left->right = new Node(1);
root->right->right = new Node(-25);
root->right->right->left = new Node(3);
root->right->right->right = new Node(4);
cout << maxPathSum(root);
return 0;
}
//Driver Code Ends }
//Driver Code Starts{
// Java program to find maximum path sum in Binary Tree
class Node {
int data;
Node left, right;
// Constructor to initialize a new node
Node(int value) {
data = value;
left = null;
right = null;
}
}
//Driver Code Ends }
class GfG {
// Returns the maximum path sum in the subtree with the current node as an endpoint.
// Also updates 'res' with the maximum path sum.
static int maxPathSumUtil(Node root, int[] res) {
// Base case: return 0 for a null node
if (root == null) return 0;
// Calculate maximum path sums for left and right subtrees
int l = Math.max(0, maxPathSumUtil(root.left, res));
int r = Math.max(0, maxPathSumUtil(root.right, res));
// Update 'res' with the maximum path sum passing through the current node
res[0] = Math.max(res[0], l + r + root.data);
// Return the maximum path sum rooted at this node
return root.data + Math.max(l, r);
}
// Returns maximum path sum in tree with given root
static int maxPathSum(Node root) {
int[] res = {root.data};
// Compute maximum path sum and store it in 'res'
maxPathSumUtil(root, res);
return res[0];
}
//Driver Code Starts{
public static void main(String[] args) {
// Representation of input binary tree:
// 10
// / \
// 2 10
// / \ \
// 20 1 -25
// / \
// 3 4
Node root = new Node(10);
root.left = new Node(2);
root.right = new Node(10);
root.left.left = new Node(20);
root.left.right = new Node(1);
root.right.right = new Node(-25);
root.right.right.left = new Node(3);
root.right.right.right = new Node(4);
System.out.println(maxPathSum(root));
}
}
//Driver Code Ends }
//Driver Code Starts{
# Python program to find maximum path sum in Binary Tree
class Node:
# Constructor to initialize a new node
def __init__(self, value):
self.data = value
self.left = None
self.right = None
//Driver Code Ends }
# Returns the maximum path sum in the subtree with the current node as an endpoint.
# Also updates 'res' with the maximum path sum.
def maxPathSumUtil(root, res):
# Base case: return 0 for a null node
if root is None:
return 0
# Calculate maximum path sums for left and right subtrees
l = max(0, maxPathSumUtil(root.left, res))
r = max(0, maxPathSumUtil(root.right, res))
# Update 'res' with the maximum path sum passing through the current node
res[0] = max(res[0], l + r + root.data)
# Return the maximum path sum rooted at this node
return root.data + max(l, r)
# Returns maximum path sum in tree with given root
def maxPathSum(root):
res = [root.data]
# Compute maximum path sum and store it in 'res'
maxPathSumUtil(root, res)
return res[0]
//Driver Code Starts{
if __name__ == "__main__":
# Representation of input binary tree:
# 10
# / \
# 2 10
# / \ \
# 20 1 -25
# / \
# 3 4
root = Node(10)
root.left = Node(2)
root.right = Node(10)
root.left.left = Node(20)
root.left.right = Node(1)
root.right.right = Node(-25)
root.right.right.left = Node(3)
root.right.right.right = Node(4)
print(maxPathSum(root))
//Driver Code Ends }
//Driver Code Starts{
// C# program to find maximum path sum in Binary Tree
using System;
class Node {
public int data;
public Node left, right;
// Constructor to initialize a new node
public Node(int value) {
data = value;
left = null;
right = null;
}
}
class GfG {
//Driver Code Ends }
// Returns the maximum path sum in the subtree with the current node as an endpoint.
// Also updates 'res' with the maximum path sum.
static int maxPathSumUtil(Node root, ref int res) {
// Base case: return 0 for a null node
if (root == null)
return 0;
// Calculate maximum path sums for left and right subtrees
int l = Math.Max(0, maxPathSumUtil(root.left, ref res));
int r = Math.Max(0, maxPathSumUtil(root.right, ref res));
// Update 'res' with the maximum path sum passing through the current node
res = Math.Max(res, l + r + root.data);
// Return the maximum path sum rooted at this node
return root.data + Math.Max(l, r);
}
// Returns maximum path sum in tree with given root
static int maxPathSum(Node root) {
int res = root.data;
// Compute maximum path sum and store it in 'res'
maxPathSumUtil(root, ref res);
return res;
}
//Driver Code Starts{
static void Main(string[] args) {
// Representation of input binary tree:
// 10
// / \
// 2 10
// / \ \
// 20 1 -25
// / \
// 3 4
Node root = new Node(10);
root.left = new Node(2);
root.right = new Node(10);
root.left.left = new Node(20);
root.left.right = new Node(1);
root.right.right = new Node(-25);
root.right.right.left = new Node(3);
root.right.right.right = new Node(4);
Console.WriteLine(maxPathSum(root));
}
}
//Driver Code Ends }
//Driver Code Starts{
// JavaScript program to find maximum path sum in Binary Tree
class Node {
constructor(value) {
// Constructor to initialize a new node
this.data = value;
this.left = null;
this.right = null;
}
}
//Driver Code Ends }
// Returns the maximum path sum in the subtree with the current node as an endpoint.
// Also updates 'res' with the maximum path sum.
function maxPathSumUtil(root, res) {
// Base case: return 0 for a null node
if (root === null) return 0;
// Calculate maximum path sums for left and right subtrees
const l = Math.max(0, maxPathSumUtil(root.left, res));
const r = Math.max(0, maxPathSumUtil(root.right, res));
// Update 'res' with the maximum path sum passing through the current node
res.value = Math.max(res.value, l + r + root.data);
// Return the maximum path sum rooted at this node
return root.data + Math.max(l, r);
}
// Returns maximum path sum in tree with given root
function maxPathSum(root) {
const res = { value: root.data };
// Compute maximum path sum and store it in 'res'
maxPathSumUtil(root, res);
return res.value;
}
//Driver Code Starts{
// Driver Code
// Representation of input binary tree:
// 10
// / \
// 2 10
// / \ \
// 20 1 -25
// / \
// 3 4
const root = new Node(10);
root.left = new Node(2);
root.right = new Node(10);
root.left.left = new Node(20);
root.left.right = new Node(1);
root.right.right = new Node(-25);
root.right.right.left = new Node(3);
root.right.right.right = new Node(4);
console.log(maxPathSum(root));
//Driver Code Ends }
Time Complexity: O(n), where n is the number of nodes in the Binary Tree.
Auxiliary Space: O(h), where h is the height of the tree.
Similar Reads
Maximum Path sum in a N-ary Tree
Given an undirected tree with n nodes numbered from 1 to n and an array arr[] where arr[i] denotes the value assigned to (i+1)th node. The connections between the nodes are provided in a 2-dimensional array edges[][]. The task is to find the maximum path sum between any two nodes. (Both the nodes ca
7 min read
Maximum spiral sum in Binary Tree
Given a binary tree containing n nodes. The task is to find the maximum sum obtained when the tree is spirally traversed. In spiral traversal one by one all levels are being traversed with the root level traversed from right to left, then the next level from left to right, then further next level fr
9 min read
Maximum in a Binary Search Tree
Given a Binary Search Tree, the task is to find the node with the maximum value in a BST. Example: Input: Output : 7 Input: Output: 20 Table of Content [Naive Approach] Using Inorder Traversal – O(n) Time and O(n) Space[Expected Approach] Iterative Approach – O(n) Time and O(1) Space[Naive Approach]
11 min read
Maximum parent children sum in Binary tree
Given a Binary Tree, find the maximum sum in a binary tree by adding the parent with its children. Exactly three Node needs to be added. If the tree does not have a node with both of its children as not NULL, return 0. We simply traverse the tree and find the Node that has the maximum sum. We need t
5 min read
Maximum XOR path of a Binary Tree
Given a Binary Tree, the task is to find the maximum of all the XOR value of all the nodes in the path from the root to leaf.Examples: Input: 2 / \ 1 4 / \ 10 8 Output: 11 Explanation: All the paths are: 2-1-10 XOR-VALUE = 9 2-1-8 XOR-VALUE = 11 2-4 XOR-VALUE = 6 Input: 2 / \ 1 4 / \ / \ 10 8 5 10 O
8 min read
Maximum product of any path in given Binary Tree
Given a binary tree of N nodes, the task is to find the maximum product of the elements of any path in the binary tree. Note: A path starts from the root and ends at any leaf in the tree. Examples: Input: 4 / \ 2 8 / \ / \2 1 3 4 Output: 128Explanation: Path in the given tree goes like {4, 8, 4} whi
5 min read
Find the maximum sum leaf to root path in a Binary Tree
Given a Binary Tree, the task is to find the maximum sum path from a leaf to a root. Example : Input: Output: 60Explanantion: There are three leaf to root paths 20->30->10, 5->30->10 and 15->10. The sums of these three paths are 60, 45 and 25 respectively. The maximum of them is 60 an
15+ min read
Count all K Sum Paths in Binary Tree
Given a binary tree and an integer k, the task is to count the number of paths in the tree such that the sum of the nodes in each path equals k. A path can start from any node and end at any node and must be downward only. Examples: Input: k = 7 Output: 3 Table of Content [Naive Approach] By Explori
15+ min read
Find maximum level sum in Binary Tree
Given a Binary Tree having positive and negative nodes, the task is to find the maximum sum level in it. Examples: Input : 4 / \ 2 -5 / \ /\ -1 3 -2 6Output: 6Explanation :Sum of all nodes of 0'th level is 4Sum of all nodes of 1'th level is -3Sum of all nodes of 0'th level is 6Hence maximum sum is 6
15+ min read
Print all k-sum paths in a binary tree
A binary tree and a number k are given. Print every path in the tree with sum of the nodes in the path as k. A path can start from any node and end at any node and must be downward only, i.e. they need not be root node and leaf node; and negative numbers can also be there in the tree. Examples: Inpu
9 min read