Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. 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).
  2. 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