Maximum path sum in a binary tree
Given a binary tree, write an efficient algorithm to find the maximum path sum between any two nodes in it. The path can start and end at any node in the tree and need not go through the root.
For example, the maximum sum path in the following binary tree is highlighted in green:
Related Post:
Find the maximum sum path between two leaves in a binary tree
We have discussed finding the maximum path sum in a binary tree that starts and ends at a leaf node in the above post. In the current problem, there is no such restriction on where the path can start or end.
A simple solution would be to traverse the tree and, for every node, calculate the maximum sum path starting from it and passing through its left and right child. Keep track of the maximum among all the maximum sum paths found and return it after all nodes are processed. The time complexity of this solution is O(n2), where n is the total number of nodes in the binary tree.
We can reduce the time complexity to linear by traversing the tree in a bottom-up manner. Each node returns the maximum path sum “starting” at that node to its parent. To ensure that the maximum path sum “starts” at that node, at most, one child of the node should be involved.
The maximum path sum passing “through” a node is the maximum of the following:
- Node’s value.
- Node’s value + maximum path sum “starting” from its left child.
- Node’s value + maximum path sum “starting” from its right child.
- Node’s value + maximum path sum “starting” from its left child + maximum path sum “starting” from its right child.
The algorithm can be implemented as follows in C++, Java, and Python. Note that the maximum path sum is passed by reference to the function (instead of returning it), and its value is updated within the function.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include <iostream> #include <limits> using namespace std; // Data structure to store a binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; // Recursive function to find the maximum path sum "starting" from the // given node in a binary tree. The maximum path sum between two nodes // in a binary tree is updated in the reference variable `result`. int findMaxPathSum(Node* node, int &result) { // base case: empty tree if (node == nullptr) { return 0; } // find maximum path sum "starting" from the left child int left = findMaxPathSum(node->left, result); // find maximum path sum "starting" from the right child int right = findMaxPathSum(node->right, result); // Try all possible combinations to get the optimal result result = max(result, node->data); result = max(result, node->data + left); result = max(result, node->data + right); result = max(result, node->data + left + right); // return the maximum path sum "starting" from the given node return max(node->data, node->data + max(left, right)); } int main() { /* Construct the following tree 1 / \ / \ 2 10 / \ / \ -1 -4 -5 -6 / / \ 3 7 4 \ -2 */ Node* root = new Node(1); root->left = new Node(2); root->right = new Node(10); root->left->left = new Node(-1); root->left->right = new Node(-4); root->right->left = new Node(-5); root->right->right = new Node(-6); root->left->right->left = new Node(4); root->right->left->left = new Node(7); root->right->left->right = new Node(4); root->right->left->left->right = new Node(-2); int result = numeric_limits<int>::min(); findMaxPathSum(root, result); cout << "The maximum path sum is " << result << endl; return 0; } |
Output:
The maximum path sum is 15
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
import java.util.concurrent.atomic.AtomicInteger; // A class to store a binary tree node class Node { int data; Node left, right; Node(int data) { this.data = data; this.left = this.right = null; } } class Main { // Recursive function to find the maximum path sum "starting" from the // given node in the binary tree. public static int findMaxPathSum(Node node, AtomicInteger result) { // base case: empty tree if (node == null) { return 0; } // find maximum path sum "starting" from the left child int left = findMaxPathSum(node.left, result); // find maximum path sum "starting" from the right child int right = findMaxPathSum(node.right, result); // Try all possible combinations to get the optimal result int max = result.get(); max = Integer.max(max, node.data); max = Integer.max(max, node.data + left); max = Integer.max(max, node.data + right); max = Integer.max(max, node.data + left + right); result.set(max); // return the maximum path sum "starting" from the given node return Integer.max(node.data, node.data + Integer.max(left, right)); } public static void main(String[] args) { /* Construct the following tree 1 / \ / \ 2 10 / \ / \ -1 -4 -5 -6 / / \ 3 7 4 \ -2 */ Node root = new Node(1); root.left = new Node(2); root.right = new Node(10); root.left.left = new Node(-1); root.left.right = new Node(-4); root.right.left = new Node(-5); root.right.right = new Node(-6); root.left.right.left = new Node(4); root.right.left.left = new Node(7); root.right.left.right = new Node(4); root.right.left.left.right = new Node(-2); AtomicInteger result = new AtomicInteger(Integer.MIN_VALUE); findMaxPathSum(root, result); System.out.println("The maximum path sum is " + result); } } |
Output:
The maximum path sum is 15
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
import sys # A class to store a binary tree node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Recursive function to find the maximum path sum "starting" from the # given node in a binary tree. The maximum path sum between two nodes # in a binary tree is updated in the `result` def findMaxPathSum(node, result=-sys.maxsize): # base case: empty tree if node is None: return 0, result # find maximum path sum "starting" from the left child left, result = findMaxPathSum(node.left, result) # find maximum path sum "starting" from the right child right, result = findMaxPathSum(node.right, result) # Try all possible combinations to get the optimal result result = max(result, node.data) result = max(result, node.data + left) result = max(result, node.data + right) result = max(result, node.data + left + right) # return the maximum path sum "starting" from the given node return max(node.data, node.data + max(left, right)), result if __name__ == '__main__': root = None ''' Construct the following tree 1 / \ / \ 2 10 / \ / \ -1 -4 -5 -6 / / \ 3 7 4 \ -2 ''' root = Node(1) root.left = Node(2) root.right = Node(10) root.left.left = Node(-1) root.left.right = Node(-4) root.right.left = Node(-5) root.right.right = Node(-6) root.left.right.left = Node(4) root.right.left.left = Node(7) root.right.left.right = Node(4) root.right.left.left.right = Node(-2) print('The maximum path sum is', findMaxPathSum(root)[1]) |
Output:
The maximum path sum is 15
The time complexity of the above solution is O(n), where n is the total number of nodes in the binary tree. The auxiliary space required by the program is O(h) for the call stack, where h is the height of the tree.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)