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.
Find maximum sum path between two leaves in a binary tree
We have discussed finding the maximum path sum in a binary tree that starts & 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 is to traverse the tree and, for every node, calculate the maximum sum path starting from it and passing through its left child 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).
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 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
77
|
#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 the 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()
{
Node* root = nullptr;
/* Construct below tree
1
/
/
2 10
/ /
-1 -4 -5 -6
/ /
3 7 4
-2
*/
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
77
|
import java.util.concurrent.atomic.AtomicInteger;
// 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)
{
Node root = null;
/* construct below tree
1
/
/
2 10
/ /
-1 -4 -5 -6
/ /
3 7 4
-2
*/
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 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 the 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 below the 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
Download Run Code
Output:
The maximum path sum is 15
Download Run Code
Output:
The maximum path sum is 15
Download Run Code
Output:
The maximum path sum is 15
The time complexity of the above solution is O(n), where n is a number of nodes in the binary tree. The auxiliary space used by the program is O(h) for the call stack, where h is the height of the tree.
source