Maximum path sum

Dec 18, 2024 • 5 mins read
Hero Image

Problem Overview

The problem "Binary Tree Maximum Path Sum" on LeetCode presents an intriguing challenge that involves finding the maximum path sum in a binary tree. A path in this binary tree is defined as a sequence of nodes connected by edges, and it can start and end at any node. This problem asks us to determine the highest possible path sum which can be obtained.

Understanding the Problem

To tackle this problem, we need to delve deeper into the structure of a binary tree. A binary tree is composed of nodes where each node has at most two children referred to as the left child and the right child. The path in this problem can be any sequence of nodes from any node to another, rather than merely a root-to-leaf path.

Consider the following binary tree structure:

       -10
       /  \
      9   20
         /  \
        15   7

In this example, the path that gives the maximum sum is 15 -> 20 -> 7, resulting in a sum of 42.

Key DSA Concepts and Theory

Binary Tree

A binary tree is a tree data structure where each node has at most two children. These trees are fundamental in computer science for organizing and storing hierarchical data.

Tree Traversals

Tree traversal is a method for visiting each node in the tree exactly once. The typical methods include:

  • Preorder (Node, Left, Right)
  • Inorder (Left, Node, Right)
  • Postorder (Left, Right, Node)

For this problem, a form of postorder traversal will be most aligned as it ensures that we calculate the path sum including both subtrees before using it at the parent node.

Depth-First Search (DFS)

DFS is a common strategy for traversing or searching through tree or graph data structures. It can be implemented using a stack or through recursion, making it a suitable approach for tree problems due to its hierarchical nature.

Solution Approach

The strategy revolves around using DFS to navigate the tree and compute the maximum path sum at each node recursively. Each node considers the highest path sum from its left and right subtrees and calculates a local maximum path sum.

Steps

  1. Define a Helper Function: This function will compute the maximum path sum for each node recursively.
  2. Compute Local Maximum Path: For each node, consider two options - traversing either to the left or the right child.
  3. Calculate the Path Using Children: Compute the path sum using the maximum possible contributions from the left and right children.
  4. Track the Global Maximum: Use a variable to track the maximum path sum found so far during the traversal.
  5. Return the Result: Once the entire tree is traversed, the tracked maximum will be the solution.

C++ Code

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int maxSum = INT_MIN;
        maxGain(root, maxSum);
        return maxSum;
    }
    
private:
    int maxGain(TreeNode* node, int &maxSum) {
        if (!node) return 0;

        int leftGain = std::max(maxGain(node->left, maxSum), 0);
        int rightGain = std::max(maxGain(node->right, maxSum), 0);

        int priceNewpath = node->val + leftGain + rightGain;

        maxSum = std::max(maxSum, priceNewpath);

        return node->val + std::max(leftGain, rightGain);
    }
};

Java Code

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    private int maxSum = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }
    
    private int maxGain(TreeNode node) {
        if (node == null) return 0;

        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        int priceNewPath = node.val + leftGain + rightGain;

        maxSum = Math.max(maxSum, priceNewPath);

        return node.val + Math.max(leftGain, rightGain);
    }
}

Time and Space Complexity Analysis

  • Time Complexity: The solution traverses each node exactly once, leading to a time complexity of (O(N)), where (N) is the number of nodes in the tree.

  • Space Complexity: The space complexity arises from the recursive stack, which can grow up to the height of the tree, (O(H)), where (H) is the height of the tree. In the worst case, (H) is (N) (in a skewed tree).

Common Mistakes to Avoid

  • Ignoring Negative Paths: Remember to ignore negative path contributions. Hence, use std::max(…, 0) or Math.max(…, 0) when calculating left and right gains.
  • Updating the Global Maximum: Ensure that you update the global maximum sum in the right place within the recursive function, considering the full path that includes both subtrees.

Similar Problems on LeetCode

Additional Resources and References

The problem exemplifies the effective use of recursive tree traversal and dynamic tracking of path sums, blending theoretical understanding and practical implementation of tree data structures.