Practice › Trees
Binary Tree Maximum Path Sum
Hard · Trees · Asked at Meta, Amazon, Google, Microsoft, DoorDash
A path is any sequence of nodes connected by edges, each used at most once; it does not have to pass through the root and has at least one node. Print the maximum possible sum of the values on a path.
Input
First line: k. Second line: k values — the tree in level order, -1 means no node.
Output
The maximum path sum.
Constraints
- 1 ≤ number of nodes ≤ 3 · 10^4
- -1000 ≤ value ≤ 1000, value ≠ -1
For each node compute the best downward path starting there (ignore negative branches). The best path "bending" at the node is value + left gain + right gain.
Example 1
Input
3 1 2 3
Output
6
Example 2
Input
7 -10 9 20 -1 -1 15 7
Output
42
Hints
- For every node, compute gain(node) = the best sum of a path that starts at the node and goes down one side. Negative branches are better ignored (gain 0).
- The best path that has its highest point at this node is val + gain(left) + gain(right). Track the maximum of that over all nodes.
Approach
Post-order recursion. gain(n) returns n.val + max(leftGain, rightGain) where each child gain is clamped at 0 — a parent can extend only one branch. While computing it, update the global answer with n.val + leftGain + rightGain, the best path that bends at n. Initialise the answer to −∞ so an all-negative tree returns its largest single value.
Complexity: O(n) time · O(h) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *left = nullptr, *right = nullptr;
Node(long long v) : val(v) {}
};
// Build a tree from level order where -1 means "no node".
Node *readTree() {
int k;
cin >> k;
vector<long long> v(k);
for (auto &x : v) cin >> x;
if (k == 0 || v[0] == -1) return nullptr;
Node *root = new Node(v[0]);
queue<Node *> q;
q.push(root);
int i = 1;
while (!q.empty() && i < k) {
Node *cur = q.front();
q.pop();
if (i < k && v[i] != -1) q.push(cur->left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.push(cur->right = new Node(v[i]));
i++;
}
return root;
}
long long best = LLONG_MIN;
long long gain(Node *n) {
if (!n) return 0;
long long a = max(0LL, gain(n->left)), b = max(0LL, gain(n->right));
best = max(best, n->val + a + b);
return n->val + max(a, b);
}
int main() {
gain(readTree());
cout << best << "\n";
return 0;
}Python solution
import sys
from collections import deque
sys.setrecursionlimit(100000)
class Node:
def __init__(self, val):
self.val, self.left, self.right = val, None, None
def build_tree(v):
"""Build a tree from level order where -1 means "no node"."""
if not v or v[0] == -1:
return None
root = Node(v[0])
q, i = deque([root]), 1
while q and i < len(v):
cur = q.popleft()
if i < len(v) and v[i] != -1:
cur.left = Node(v[i])
q.append(cur.left)
i += 1
if i < len(v) and v[i] != -1:
cur.right = Node(v[i])
q.append(cur.right)
i += 1
return root
data = list(map(int, sys.stdin.read().split()))
k = data[0]
root = build_tree(data[1 : 1 + k])
rest = data[1 + k :]
best = float("-inf")
def gain(n):
global best
if not n:
return 0
a, b = max(0, gain(n.left)), max(0, gain(n.right))
best = max(best, n.val + a + b)
return n.val + max(a, b)
gain(root)
print(best)Java solution
import java.util.*;
public class Main {
static class Node {
long val;
Node left, right;
Node(long v) { val = v; }
}
// Build a tree from level order where -1 means "no node".
static Node readTree(Scanner sc) {
int k = sc.nextInt();
long[] v = new long[k];
for (int i = 0; i < k; i++) v[i] = sc.nextLong();
if (k == 0 || v[0] == -1) return null;
Node root = new Node(v[0]);
ArrayDeque<Node> q = new ArrayDeque<>();
q.add(root);
int i = 1;
while (!q.isEmpty() && i < k) {
Node cur = q.poll();
if (i < k && v[i] != -1) q.add(cur.left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.add(cur.right = new Node(v[i]));
i++;
}
return root;
}
static long best = Long.MIN_VALUE;
static long gain(Node n) {
if (n == null) return 0;
long a = Math.max(0, gain(n.left)), b = Math.max(0, gain(n.right));
best = Math.max(best, n.val + a + b);
return n.val + Math.max(a, b);
}
public static void main(String[] args) {
gain(readTree(new Scanner(System.in)));
System.out.println(best);
}
}Solve Binary Tree Maximum Path Sum online · All practice problems