Start learning free

LESSON 405 OF 535 · BINARY TREES

Binary Tree Maximum Path Sum in C++: Recursion in O(n)

Practice O(n) Read the full explanation

A path in a binary tree is a sequence of nodes where each node is connected by an edge to the next one, and no node appears twice. A path has at least one node, and it doesn't have to go through the root.

The path sum is the sum of the values of the nodes on the path.

Given the root of a binary tree, return the largest path sum of any path in the tree.

The trees below are written in level order (top to bottom, left to right), with NULL for a missing child.

 

Example 1:

    1
   / \
  2   3

Input: root = [1,2,3]
Output: 6
Explanation: The best path is 2 → 1 → 3, with the sum 2 + 1 + 3 = 6.

Example 2:

   -10
   /  \
  9    20
      /  \
     15   7

Input: root = [-10,9,20,NULL,NULL,15,7]
Output: 42
Explanation: The best path is 15 → 20 → 7, with the sum 15 + 20 + 7 = 42. Going on to the root would add -10 and lower the sum.

Example 3:

   -2
   /  \
 -1    -3

Input: root = [-2,-1,-3]
Output: -1
Explanation: Every value is negative, so every longer path has a smaller sum. The best path is the single node -1.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 3 * 104].
  • Each node value is between -1000 and 1000.
  • The tree is at most 400 levels deep.

Note:

The solution should run in O(n) time, where n is the number of nodes: visit each node once.

STEP 1 OF 10
    Ctrl + Enter to check

    C++ · BINARY TREES

    Binary Tree Maximum Path Sum in C++, explained

    Problem overview

    A path in a binary tree is a sequence of nodes where each node is joined by an edge to the next, with no node repeated. It has at least one node, and it doesn't need to pass through the root. The path sum is the sum of the node values on it. The method maxPathSum receives the root of a tree with at least one node and returns the largest path sum of any path in the tree. The lesson provides TreeNode, with an int val and two TreeNode * fields, left and right.

    For the tree with root 1 and children 2 and 3, the best path is 2, 1, 3 with sum 6. For the tree with root -10, left child 9 and right child 20 (whose children are 15 and 7), the best path is 15, 20, 7 with sum 42: going on to the root would add -10. For the tree with root -2 and children -1 and -3 the answer is -1, the single node, because every value is negative.

    Approach: every node as the top of a path

    Every path has a highest node, the one closest to the root, and from there it goes down on at most two sides, one into the left subtree and one into the right. So the best path overall is the best one among all nodes, each tried as that top node.

    For a node, the best path with that node on top is its value plus the best downward path on the left plus the best downward path on the right. A downward path here starts at a child and keeps going down through one child at a time. If a side's best sum is negative, it only lowers the total, so that side is left out, which is the same as using 0.

    The recursive helper maxGain(node) returns the best sum of a path that starts at node and goes straight down, or stops at node itself. This is the quantity a parent needs: a parent can extend a path through one child only. A path that has already bent at the child, using both of its sides, can't also continue up to the parent, because the node would be left with three neighbours on the path.

    So each call does two jobs. It updates a running best using both sides (the bent path with this node on top), and it returns only the larger side (the straight path the parent may extend). Every node is visited once, so the time is O(n).

    Step by step

    1. Keep the best sum in a member, an int named best, so that maxGain can update it and maxPathSum can read it at the end.
    2. Initialise it to root->val in maxPathSum. A path needs at least one node and all values may be negative, so 0 would be a wrong starting point: it could be higher than every real path.
    3. Call maxGain(root). The walk updates best, so the returned value is not needed.
    4. Return best.
    5. Write maxGain(TreeNode* node) above maxPathSum, returning an int.
    6. Stop at an empty subtree: if node == NULL, return 0, since nothing adds nothing to a path.
    7. Get the left gain as max(0, maxGain(node->left)), so a negative side counts as 0. Store it in left.
    8. Do the same for the right child, storing the value in right. Both children are processed before the node itself, since the node needs their answers.
    9. Try this node as the top: set best to the larger of best and node->val + left + right.
    10. Return the straight path a parent can extend: node->val + max(left, right).

    The solution in C++

    class Solution {
public:
    int best;

    int maxGain(TreeNode* node) {
        if (node == NULL) {
            return 0;
        }
        int left = max(0, maxGain(node->left));
        int right = max(0, maxGain(node->right));
        best = max(best, node->val + left + right);
        return node->val + max(left, right);
    }

    int maxPathSum(TreeNode* root) {
        best = root->val;
        maxGain(root);
        return best;
    }
};

    Tracing the tree with root -10, children 9 and 20, and 20's children 15 and 7, with best starting at -10:

    maxGain(15) returns 15
maxGain(7)  returns 7
maxGain(20) returns 35, best becomes 42 (15 + 20 + 7)
maxGain(9)  returns 9
maxGain(-10) returns 25, best stays 42 (9 - 10 + 35 = 34)

    The root's call returns 25, but that return value is unused: the answer is best, which stays 42.

    C++ details worth a closer look:

    • A member as shared state. best is a data member, so every call of maxGain sees the same variable. It is set in maxPathSum before the walk, so a second call on another tree starts fresh. Nothing in the class initialises it otherwise: an int member has no defined value until assigned.
    • max with two int arguments. max(0, maxGain(...)) compiles because both arguments have the same type. Mixing, say, int and long long would not deduce a single type.
    • NULL. The node type's constructor uses NULL for missing children, so the base case compares with NULL as well. nullptr would behave the same.
    • Return value and side effect. maxGain returns one thing (the straight path) and records another (the bent path) in best. Keeping the two apart is the heart of the solution.
    • Overflow. Values are at most 1000 in absolute value and there are at most 30,000 nodes, so the sums stay far below the int limit.

    Complexity

    Time: O(n). Each node is visited once, and each visit does a constant amount of work: two max calls, an addition and a comparison.

    Space: O(h), where h is the height of the tree, for the recursion stack. The constraints limit the depth to 400 levels, so the stack stays small. In a balanced tree h is about log n, and in a chain it is n.

    Edge cases and common mistakes

    • All values negative. The root with children -1 and -3 under -2 returns -1. Starting best at 0 would return 0, a sum no path has. The negative sides are clamped to 0 inside maxGain, but best still has to start at a real path.
    • A single node. A tree of one node returns that value: 5 gives 5, and -7 gives -7.
    • A path that skips the root. The 42 above never touches the root. This is why every node is tried as the top, not only the root.
    • A path that bends below the root. In the tree with root 1 and one child, -5, which has children 10 and 9, the answer is 14: the path 10, -5, 9 bends at -5. Adding the root would help only if the path through -5 could carry on up, but the best straight path from -5 is 5 (-5 + 10), so the root would give just 6.
    • Returning both sides. If maxGain returned node->val + left + right, a parent could extend a path that already uses both sides of a node, and the sum would belong to no real path.
    • Forgetting to clamp. Without max(0, ...), a negative subtree is always added, which lowers the sums and can miss the best path.
    • Using left + right in the return. Only one side can continue upward.

    Testing

    • Root 1 with children 2 and 3 gives 6.
    • Root -10, children 9 and 20, with 20's children 15 and 7, gives 42.
    • Root -2 with children -1 and -3 gives -1.
    • A single node 5 gives 5, and a single node -7 gives -7.
    • Root 2 with children -1 and 3 gives 5.
    • Root 1 with left child -5 (which has children 10 and 9) and no right child gives 14.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free