Binary Tree Maximum Path Sum

Finding the maximum path sum in a binary tree can be solved using a recursive approach. The recursive function will return two values: the maximum path sum through the current node (considering only one of its subtrees), and the maximum path sum found so far in the tree (this can be across any path in the tree).

Here are the steps:

  1. Base Case: If the current node is None, return a negative infinity value for both the local and global maximum path sums.
  2. Recursive Calls: Call the recursive function for the left and right children of the current node. Get the local and global maximum path sums for the left and right subtrees.
  3. Compute Local Maximum: The local maximum path sum through the current node is the maximum of the current node’s value, the current node’s value plus the left child’s local maximum, and the current node’s value plus the right child’s local maximum.
  4. Compute Global Maximum: The global maximum path sum for the current subtree is the maximum of the left and right children’s global maximum, and the sum of the current node’s value with its left and right children’s local maximums.
  5. Return Values: Return the local and global maximum path sums for the current node.

Here’s the code implementing this approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        def helper(node):
            nonlocal max_sum
            if not node:
                return 0

            # Compute the maximum path sum through the left and right children
            left_max = max(helper(node.left), 0)
            right_max = max(helper(node.right), 0)

            # Compute the maximum path sum through the current node
            local_max = node.val + left_max + right_max

            # Update the global maximum if the local maximum is greater
            max_sum = max(max_sum, local_max)

            # Return the maximum path sum that includes the current node and one of its children
            return node.val + max(left_max, right_max)

        max_sum = float('-inf')
        helper(root)
        return max_sum

Key Takeaways:

  • The recursive approach enables considering all possible paths through the tree.
  • The function keeps track of both the local maximum path sum through the current node and the global maximum path sum across the whole tree.
  • The time complexity is (O(n)), where (n) is the number of nodes in the tree, as each node is visited once.
  • The space complexity is (O(h)), where (h) is the height of the tree, corresponding to the maximum depth of the recursive call stack.

We’ll make use of a helper function to compute the maximum path sum through a node and also keep track of the maximum path sum across any path in the tree using an outer variable.

Key Takeaways:

  • The recursive function helper computes the maximum path sum that includes the current node and one of its children (either left or right).
  • The variable max_sum keeps track of the maximum path sum across any path in the tree.
  • By ensuring that negative values are replaced with 0 (using max(helper(node.left), 0)), we avoid including paths that would decrease the total sum.
  • The time complexity remains (O(n)), and the space complexity remains (O(h)), where (n) is the number of nodes and (h) is the height of the tree.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end


1. Objective: Maximum Path Sum

2. What are the different paths that we need to consider?
    - Example 1: Path passes through the root
    - Example 2: Path is passing through the parent
    - Example 3: Path can be skewed
    
        Can I have path that does not include the parent? Yes
    
3. Node #: 1
    Return: node.val
   Handle leaf node: if node.nil?
                        return 0
                        
4. Recursive Approach 
    Problem Decomposition
     Unit of Work
     - Ask left subtree to give me your max path sum
     - Ask right subtree to give me your max path sum
     - max(left, right) + root.val (Root is part of the path)
     
     Example 1: join the left and right and pass through the root
     left = 2
     right = 3
     
     As long as the root is positive, we can add to the max of left and right
     or to the joined left and right
     
     max(left, right), 
     left+right+root
     left+root, 
     right+root
     
     What if the left and right gave negative and root was positive.
     
5. What does the root need to get from its children to perform the unit of work?
    Children need to return the max path sum in their subtree
    
6. We have to perform the unit of work after the recursive calls return

7. We return the max path sum for a given smaller subtree 

8. How do we keep track of max_sum, return value?
    Return value from the recursive function    



def max_gain(node)
    if node.nil?
        return 0
    end

    left = max_gain(node.left)
    right = max_gain(node.right)

    @max_sum = [@max_sum, left + right + node.val].max

    return [0, node.val + [left, right].max].max
end

# @param {TreeNode} root
# @return {Integer}
def max_path_sum(root)
   @max_sum = -Float::INFINITY
   max_gain(root)
   @max_sum
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end

class Solution {
  int max_sum = Integer.MIN_VALUE;

  public int max_gain(TreeNode node) {
    if (node == null) return 0;

    // max sum on the left and right sub-trees of node
    int left_gain = Math.max(max_gain(node.left), 0);
    int right_gain = Math.max(max_gain(node.right), 0);

    // the price to start a new path where `node` is a highest node
    int price_newpath = node.val + left_gain + right_gain;

    // update max_sum if it's better to start a new path
    max_sum = Math.max(max_sum, price_newpath);

    // for recursion :
    // return the max gain if continue the same path
    return node.val + Math.max(left_gain, right_gain);
  }

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

def max_gain(node) if node.nil? return 0 end

left_gain = [max_gain(node.left), 0].max
right_gain = [max_gain(node.right), 0].max

price_new_path = node.val + left_gain + right_gain
@max_sum = [@max_sum, price_new_path].max

return node.val + [left_gain, right_gain].max

end

@param {TreeNode} root

@return {Integer}

def max_path_sum(root) @max_sum = -Float::INFINITY max_gain(root) @max_sum end


## Identifying Problem Isomorphism

"124. Binary Tree Maximum Path Sum" involves finding a path that has the maximum sum of node values in a binary tree, where a path can start and end at any node.

A similar problem in terms of structure and solving strategy is "543. Diameter of Binary Tree". This problem requires finding the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The two problems are isomorphic because they both require a form of depth-first search to traverse the binary tree and find the maximum path or diameter. The depth-first search is used to traverse to the furthest nodes and then back up, aggregating values from the subtrees to calculate the longest path or the maximum sum.

While the two problems share a similar structure and solving strategy, they are not exactly identical. One is looking for the maximum sum of node values, while the other is looking for the maximum number of edges. So, while structurally isomorphic, they represent different specific problems.

The problem "Binary Tree Maximum Path Sum" requires a good understanding of binary trees and recursion. Here are 10 problems that can help you prepare for it:

1. [104. Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/): It is a simpler problem that can help you understand the depth of a binary tree.

2. [100. Same Tree](https://leetcode.com/problems/same-tree/): You can practice tree traversal and comparing two trees.

3. [101. Symmetric Tree](https://leetcode.com/problems/symmetric-tree/): This problem will help you to understand the symmetry of a tree, which can be crucial in other tree-related problems.

4. [110. Balanced Binary Tree](https://leetcode.com/problems/balanced-binary-tree/): It can help you understand the balance of a binary tree.

5. [112. Path Sum](https://leetcode.com/problems/path-sum/): This problem involves traversal to find a path that sums up to a target, similar to the main problem but easier.

6. [124. Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/): Although it's not a "lesser complexity" problem, solving it would directly help you understand the problem at hand.

7. [543. Diameter of Binary Tree](https://leetcode.com/problems/diameter-of-binary-tree/): This problem is similar to the main problem in the sense that you need to consider the sum of two paths.

8. [687. Longest Univalue Path](https://leetcode.com/problems/longest-univalue-path/): This is another problem where you need to consider the path through the tree.

9. [968. Binary Tree Cameras](https://leetcode.com/problems/binary-tree-cameras/): This problem requires considering paths through the tree.

10. [113. Path Sum II](https://leetcode.com/problems/path-sum-ii/): An extension of the path sum problem, which requires storing the actual paths, not just their sums.

These cover tree traversal, recursion and how to track the maximum/minimum path sum in a binary tree.

## Clarification Questions

What are the clarification questions we can ask about this problem?

## Identifying Problem Isomorphism

Can you help me with finding the isomorphism for this problem?

Which problem does this problem map to the corresponding isomorphic problem on Leetcode ?


```python
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.res = float('-inf')
        self.helper(root)
        return self.res 
        
    def helper(self, root):
        if not root:
            return 0
        left, right = self.helper(root.left), self.helper(root.right)
        self.res = max(self.res, root.val + left + right)
        return max(root.val + max(left, right), 0)

Binary Tree Maximum Path Sum - The problem requires identifying the path in a binary tree that leads to the maximum sum. This involves understanding the properties of paths in a graph, hence it’s classified under Path Analysis in Graphs.

Binary Tree Maximum Path Sum - The problem asks for the path in a binary tree that leads to the maximum sum. This is about understanding the properties of paths in a tree, so it’s Tree Path Analysis.

Language Agnostic Coding Drills

Let’s break this down into its smallest units of learning:

  1. Basic Syntax and Variables Understanding how to define variables and basic syntax in the programming language.

  2. Understanding Basic Data Types Understanding integers, floating point numbers, strings, booleans, etc.

  3. Conditional Statements Understanding if-else conditional statements to control the flow of your program.

  4. Defining and Instantiating Classes Understanding how to define classes and create instances of those classes.

  5. Defining Class Variables Understanding how to define variables that are associated with the class itself, not instances of the class.

  6. Working with Trees Understanding the tree data structure and how to traverse trees using recursion.

  7. Working with None Understanding the concept of None (or equivalent in other languages), and how it can be used to denote the absence of a value or a null condition.

  8. Recursion Understanding the concept of recursion, where a function calls itself in its definition.

  9. Return Statements Understanding how to use return statements in functions, and how they control the flow of the program.

  10. Working with Binary Trees Understanding the specific properties of binary trees, such as left and right children.

  11. Max Function Understanding the max() function (or equivalent in other languages) and how it can be used to easily compare values.

Here are some coding drills associated with these units of learning:

  1. Write a program that assigns an integer to a variable and then prints that variable.

  2. Write a program that assigns a string to a variable and prints the string, then assigns an integer to the variable and prints the integer.

  3. Write a program that uses an if-else statement to print different messages based on the value of a boolean variable.

  4. Define a class with a method that prints a message, then create an instance of that class and call the method.

  5. Add a class variable to the class from the previous exercise, then print the class variable from an instance of the class.

  6. Write a function that traverses a simple tree structure (represented with nested lists or a similar data structure) using recursion.

  7. Write a function that takes a variable as input and returns a different value based on whether the input is None or not.

  8. Write a recursive function that calculates the factorial of a number.

  9. Write a function that returns a value, and show how this value can be assigned to a variable.

  10. Define a class for a binary tree node, and write a function that creates a binary tree with at least three levels.

  11. Write a function that uses the max() function to return the maximum of three inputs.

Let’s break down this problem into individual concepts, describe them, and create language-agnostic drills for them:

  1. Defining a Class/Object: In this case, a binary tree node is represented as an object (or class) with three attributes: a value, and two pointers for the left and right children.

    Drill: Create a class (or equivalent structure in your language) for a car, with attributes for the brand, model, and year.

  2. Understanding Recursion: Recursion is a process where a function calls itself as its subroutine. This property is used to traverse the binary tree in this problem.

    Drill: Write a recursive function that computes the factorial of a number.

  3. Understanding Trees: A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child.

    Drill: Given a binary tree, write a function that prints out the values of each node in a depth-first search manner.

  4. Finding Maximum Value: The solution involves finding the maximum value amongst multiple variables, or potential outcomes.

    Drill: Write a function that finds the maximum value in an array of integers.

  5. Problem Specific Drill - Understanding Path in Trees: The problem requires understanding the concept of a “path” in a binary tree. A path in a binary tree is a sequence of nodes where each pair of consecutive nodes in the sequence are connected.

    Drill: Write a function that calculates the length of the longest path in a binary tree.

In solving this problem, the approach was to recursively traverse the tree, at each node calculating the maximum path that includes the current node and updating the global maximum path sum (self.res) if necessary. The maximum path that includes the current node is calculated by adding the current node’s value and the maximum of the maximum paths from the left and right children. The maximum path from a child is calculated in the same manner. This process is started by calling the helper function on the root of the tree.

Targeted Drills in Python

Let’s turn those drills into Python exercises:

  1. Basic Syntax and Variables
1
2
3
4
5

# Define a variable and assign it an integer value of 10.
# Print the value of the variable.

num = 10
print(num)
  1. Understanding Basic Data Types
1
2
3
4
5
6
7
8

# Assign a string to a variable and print the variable.
# Assign an integer to the variable and print the variable.

data = "Hello, world!"
print(data)

data = 42
print(data)
  1. Conditional Statements
1
2
3
4
5
6
7
8

# Use an if-else statement to print different messages based on the value of a boolean variable.

flag = True

if flag:
    print("The flag is true!")
else:
    print("The flag is false!")
  1. Defining and Instantiating Classes
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# Define a class with a method that prints a message.
# Create an instance of that class and call the method.

class MyClass:
    def say_hello(self):
        print("Hello!")

# Create an instance of MyClass and call say_hello
obj = MyClass()
obj.say_hello()
  1. Defining Class Variables
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# Add a class variable to MyClass.
# Print the class variable from an instance of the class.

class MyClass:
    greeting = "Hello!"

    def say_hello(self):
        print(self.greeting)

# Create an instance of MyClass and print the greeting
obj = MyClass()
print(obj.greeting)
  1. Working with Trees
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# A simple binary tree can be represented as nested lists. Here's an example:
# tree = [1, [2, [4, None, None], [5, None, None]], [3, None, None]]
# Write a function that prints all the values in the tree.

def print_tree(tree):
    if tree is None:
        return
    print(tree[0])  # print the root value
    print_tree(tree[1])  # recurse on the left subtree
    print_tree(tree[2])  # recurse on the right subtree
  1. Working with None
1
2
3
4
5
6
7

# Write a function that takes a variable as input and returns a different message based on whether the input is None or not.

def check_none(value):
    if value is None:
        return "The value is None!"
    else:
        return "The value is not None!"
  1. Recursion
1
2
3
4
5
6
7

# Write a recursive function that calculates the factorial of a number.

def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)
  1. Return Statements
1
2
3
4
5
6
7
8

# Write a function that returns a value, and show how this value can be assigned to a variable.

def square(n):
    return n * n

# Assign the return value of square(5) to a variable and print it
result = square(5)
print(result)
  1. Working with Binary Trees
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

# Define a class for a binary tree node, and write a function that creates a binary tree with at least three levels.

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# Function to create a binary tree
def create_tree():
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    return root
  1. Max Function
1
2
3
4
5
6



# Write a function that uses the max() function to return the maximum of three inputs.

def max_of_three(a, b, c):
    return max(a, b, c)

Here are more Python drills:

  1. Defining a Class/Object:

    Drill: Create a class for a car, with attributes for the brand, model, and year.

1
2
3
4
5

class Car:
    def __init__(self, brand, model, year):
        self.brand = brand
        self.model = model
        self.year = year

  1. Understanding Recursion:

    Drill: Write a recursive function that computes the factorial of a number.

1
2
3
4
5

def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)

  1. Understanding Trees:

    Drill: Given a binary tree, write a function that prints out the values of each node in a depth-first search manner.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def dfs(node):
    if node is not None:
        print(node.value)
        dfs(node.left)
        dfs(node.right)

  1. Finding Maximum Value:

    Drill: Write a function that finds the maximum value in an array of integers.

1
2

def max_value(nums):
    return max(nums)

  1. Problem Specific Drill - Understanding Path in Trees:

    Drill: Write a function that calculates the length of the longest path in a binary tree.

1
2
3
4
5
6
7

def max_depth(node):
    if node is None:
        return 0
    else:
        left_depth = max_depth(node.left)
        right_depth = max_depth(node.right)
        return max(left_depth, right_depth) + 1