What is the time complexity of Binary Tree Maximum Path Sum?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Binary Tree Maximum Path Sum?

This problem uses Dynamic Programming, Tree, Depth-First Search, Binary Tree. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Binary Tree Maximum Path Sum?

Insight 1: The maximum path sum can be a path between any two nodes in the tree, not necessarily passing through the root or any specific node. Insight 2: A path can either extend from a node to one of its children or form a 'V' shape through the node, utilizing both children. We need to consider both possibilities.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Binary Tree Maximum Path Sum - LeetCode 124 Solution

Q: Which companies ask LeetCode 124. Binary Tree Maximum Path Sum in interviews?

This problem is frequently asked at Arcesium, Arista Networks, Baidu, Citadel, Datadog and 17 more companies.

Binary Tree Maximum Path Sum - Complete Solution Guide

Binary Tree Maximum Path Sum is LeetCode problem 124, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once . Note that the path does not need to pass through the root. The path sum of a path is the sum of the node's values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty path . Example 1: Input: root = [1,2,3] Output: 6 Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2

Detailed Explanation

The problem asks us to find the maximum path sum in a binary tree. A path is a sequence of nodes where adjacent nodes are connected by an edge. A node can appear in the sequence only once, and the path doesn't necessarily have to pass through the root. The path sum is the sum of the node values in the path, and we need to return the largest possible path sum among all possible paths. Constraints include the number of nodes being between 1 and 30,000, and node values being between -1000 and 1000.

Solution Approach

The solution uses a Depth-First Search (DFS) approach. For each node, we recursively calculate the maximum path sum in its left and right subtrees. The DFS function returns the maximum path sum that can be obtained by starting at that node and going down to one of its descendants (or stopping at the node itself). During the recursion, we also update a global `max_sum` variable with the maximum path sum that can be obtained by passing through the current node (forming a 'V' shape). Negative gains from the left or right subtrees are discarded by taking the maximum with 0.

Step-by-Step Algorithm

Step 1: Initialize a global variable `max_sum` to negative infinity to keep track of the maximum path sum found so far.
Step 2: Define a recursive function `dfs(node)` that takes a node as input.
Step 3: Base case: If the node is null, return 0.
Step 4: Recursively calculate the maximum gain from the left subtree (`left_gain`) and the right subtree (`right_gain`) by calling `dfs` on the left and right children, respectively. Take the maximum of the returned value and 0 to discard negative gains.
Step 5: Calculate the maximum path sum that passes through the current node (`current_path_sum`) by adding the node's value, `left_gain`, and `right_gain`.
Step 6: Update `max_sum` with the maximum of its current value and `current_path_sum`.
Step 7: Return the maximum gain that a parent node can get by extending a path from the current node. This is the node's value plus the maximum of `left_gain` and `right_gain`.
Step 8: Call `dfs(root)` to start the recursion from the root node.
Step 9: Return the final `max_sum`.

Key Insights

Insight 1: The maximum path sum can be a path between any two nodes in the tree, not necessarily passing through the root or any specific node.
Insight 2: A path can either extend from a node to one of its children or form a 'V' shape through the node, utilizing both children. We need to consider both possibilities.
Insight 3: Negative node values can reduce the path sum, so we should avoid including subtrees that only contribute negative values to the sum.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(h)

Topics

This problem involves: Dynamic Programming, Tree, Depth-First Search, Binary Tree.

Companies

Asked at: Arcesium, Arista Networks, Baidu, Citadel, Datadog, Directi, DoorDash, Flipkart, Hotstar, Intuit, Nutanix, Nvidia, Oracle, Patreon, Salesforce, Samsung, Snap, TikTok, Uber, Walmart Labs, Wix, Yandex.

Binary Tree Maximum Path Sum | LeetCode 124

Hard

Dynamic Programming Tree Depth-First Search Binary Tree

Time: O(n)Space: O(h)

Solution Code

Available in:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int max_sum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max_sum;
    }

    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // Recursively find the max path sum of the left and right subtrees
        // A path can't be extended with a negative gain, so we take max with 0
        int left_gain = Math.max(dfs(node.left), 0);
        int right_gain = Math.max(dfs(node.right), 0);

        // Check if a path through the current node is the new maximum
        // This path is a "V" shape, using both left and right children
        int current_path_sum = node.val + left_gain + right_gain;
        max_sum = Math.max(max_sum, current_path_sum);

        // Return the maximum gain a parent node can get by extending a path here
        // This is a "straight" path, so it can only include one of the children
        return node.val + Math.max(left_gain, right_gain);
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 124: Binary Tree Maximum Path Sum - Detailed explanation and solution approaches.

Topics

Dynamic Programming Tree Depth-First Search Binary Tree

Companies

ArcesiumArista NetworksBaiduCitadelDatadogDirectiDoorDashFlipkart

Stats

Difficulty:Hard

Languages:4

Companies:22

Problem #:124

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

9 steps

1
Step 1: Initialize a global variable `max_sum` to negative infinity to keep track of the maximum path sum found so far.
2
Step 2: Define a recursive function `dfs(node)` that takes a node as input.
3
Step 3: Base case: If the node is null, return 0.
4
Step 4: Recursively calculate the maximum gain from the left subtree (`left_gain`) and the right subtree (`right_gain`) by calling `dfs` on the left and right children, respectively. Take the maximum of the returned value and 0 to discard negative gains.
5
Step 5: Calculate the maximum path sum that passes through the current node (`current_path_sum`) by adding the node's value, `left_gain`, and `right_gain`.
6
Step 6: Update `max_sum` with the maximum of its current value and `current_path_sum`.
7
Step 7: Return the maximum gain that a parent node can get by extending a path from the current node. This is the node's value plus the maximum of `left_gain` and `right_gain`.
8
Step 8: Call `dfs(root)` to start the recursion from the root node.
9
Step 9: Return the final `max_sum`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(h)

📝

Why?

The time complexity is O(n) because the dfs function visits each node once. The space complexity is determined by the maximum depth of the recursion stack, which is proportional to the height of the tree. In the worst-case scenario (a skewed tree), the height can be equal to the number of nodes (n), leading to O(n) space complexity. In a balanced tree, the height is logarithmic in the number of nodes, resulting in O(log n) space complexity.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Iterative Approach (using Stack)

An iterative approach using a stack could be used to simulate the DFS traversal. This avoids the recursion stack overhead but may be more complex to implement.

Time: O(n)Space: O(n) in worst case (skewed tree)

Trade-offs: While it removes recursion, the iterative solution is more complex and might not offer substantial performance benefits in practice, given the relatively small input size. Use if stack overflow is a concern with very large, skewed trees.

✨

Key Insights

1Insight 1: The maximum path sum can be a path between any two nodes in the tree, not necessarily passing through the root or any specific node.
2Insight 2: A path can either extend from a node to one of its children or form a 'V' shape through the node, utilizing both children. We need to consider both possibilities.
3Insight 3: Negative node values can reduce the path sum, so we should avoid including subtrees that only contribute negative values to the sum.

📚

Key Terms Explained

For Students

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Tree

Hierarchical structure with nodes. Like a family tree!

Edge Cases

Edge case 1: Tree with only one node. The solution correctly handles this case because the DFS will return the node's value, and `max_sum` will be updated accordingly.
Edge case 2: Tree with all negative values. The `max(dfs(node.left), 0)` ensures that no negative subtree sum is included if it decreases the path sum. The result will be the largest single node value.
Edge case 3: Root is null. The DFS handles the null case gracefully by returning 0 and not affecting the overall maximum sum.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not considering paths that do not pass through the root. Many beginners focus only on paths that start at the root, missing the 'V' shaped paths entirely contained within a subtree.

✗Common mistake 2: Not handling negative values correctly. It's important to avoid including subtrees that only decrease the overall path sum.

✗Common mistake 3: Incorrectly updating the global maximum. The global maximum must be updated whenever a potential maximum path is found, specifically when the 'V' shape path through a node is considered.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Analyzing network graphs to find the most 'valuable' path between two points, where value could represent bandwidth, throughput, or some other performance metric. The weights could be positive or negative based on the network health.

🏦Real-world scenario 2: Finding the most profitable sequence of trades in a stock market simulation, where each trade has an associated profit or loss (represented by positive or negative node values). The optimal path could represent the trading strategy that maximizes profit.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Start with recursion, then memoize. The hardest part is identifying the state. Ask yourself: "What information do I need to make the current decision?"

🎯 Interview Tip

It's okay to not finish hard problems in interviews. Show your problem-solving process.

⚠️ Watch Out

Forgetting base cases or initializing the DP array incorrectly. Start by solving the smallest subproblems.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 3, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 13

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 6

❓

Frequently Asked Questions

How do I identify if a problem needs dynamic programming?

DP problems typically have: 1) Overlapping subproblems (same calculation repeated), 2) Optimal substructure (optimal solution uses optimal solutions to subproblems). Look for keywords like "minimum/maximum," "count ways," "is it possible," or "longest/shortest."

How do I choose between recursive and iterative tree traversal?

Use recursive traversal for cleaner code when stack depth isn't a concern (tree height < ~1000). Use iterative with explicit stack for very deep trees to avoid stack overflow. Iterative is also preferred when you need fine-grained control over the traversal process.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Binary Tree Maximum Path Sum"?

For this hard-level Dynamic Programming problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether tree techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?