The Blind 75 Leetcode Series: Binary Tree Maximum Path Sum

Photo by Chris Ried on Unsplash

Today, we are working on 124. Binary Tree Maximum Path Sum

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.

We are given a binary tree with node values. We want to find the max sum of any possible path. A path is simply a sequence of nodes where they are connected by a branch. We are not allowed to revisit the same node. We don’t need to return the path itself, just the sum.

Some possible questions we can ask are

1. are the node values always numbers? Do we need to worry about non-number value like strings?
2. Do we expect empty trees? Do we simply return 0 in that case?

If the answers are that we don’t need to worry about non-number node value and we do expect to see empty tree and should return 0, we have the information we need to proceed.

For any binary tree, we always expect a root and 0–2 children. If there’s no child node, then we just need to return the node value itself. If there’s 1 child, we check the node value itself, the child node value itself, and the sum of those two to find possible sum. With 2 children, it has more combinations. We have the 3 nodes by themselves, the combination of the node and one of the child, and the combination of all 3 nodes.

Now to get the max of this subproblem, we want to make sure the combination is returning a positive number, otherwise we will make the sum smaller as we move up the tree. If a subproblem is returning negative number at its root, we might as well discard this branch completely (treat it as null node without children, thus return 0)

With a bigger tree, we should be able to dissect the problem into smaller sub-problems and ultimately reduce it to the base case mentioned above. Then we track the answer of this base case and build it up to the full tree.

For each step, we also need to track the current max against the overall max. At the end, we return the overall max as our final answer.

We can start with our subproblem:

max_sum = float('-inf')  # max_sum should be seeable outside of the function
def find_sub_tree_max(node):
    # null node should return 0 for the "sum"
    if not node:
        return 0 
    # if the sum from left actually returns negative number, we don't want to add it to current node, use 0 instead 
    left_sum = max(find_sub_tree_max(node.left), 0)  
    # same idea for the right sum
    right_sum = max(find_sub_tree_max(node.right), 0)
    # sum at this given node
    current_sum = node.val + left_sum + right_sum  
    # update max_sum at this level
    max_sum = max(max_sum, current_sum)  
    # return this sum up one level. The reason for not returning the sum of all 3 nodes is because we can only take 1 path up, either with left child or right child. The 3-node-sum MIGHT be the new max, but we cannot pass it upward.
    return node.val + max(left_sum, right_sum)

That should do for our subproblem. For our main problem, we just have to pass in the root into the subproblem and it should take care of itself.

# again, max_sum should be outside of this function
def maxPathSum(root):
    if not root:
        return 0
    find_sub_tree_max(root)
    return max_sum

The way we write this solution is using 2 def to follow our format for answers until now, but it’d be better if everything fit in a class and we define these functions and variables as part of class attributes. Otherwise max_sum would appear out of nowhere in the function and you wouldn’t know it’s updated as the process goes when you only look at the maxPathSum function. It’s hard to maintain and prone to errors as you refactor. However, for the purpose of this problem and fitting to our format, we keep it this way.

The overall solution looks like

max_sum = float('-inf')
def find_sub_tree_max(node):
    if not node:
        return 0
    left_sum = max(find_sub_tree_max(node.left), 0)
    right_sum = max(find_sub_tree_max(node.right), 0)
    current_sum = node.val + left_sum + right_sum
    max_sum = max(max_sum, current_sum)
    return node.val + max(left_sum, right_sum)
def maxPathSum(root):
    if not root:
        return 0
    find_sub_tree_max(root)
    return max_sum

What’s our time complexity?

We go through the entire tree and update max_sum as we go. The summation, max, etc. are all O(1) operations, so we are looking at O(N) for N nodes.

max_sum = float('-inf')
def find_sub_tree_max(node):
    if not node:  # O(1)
        return 0
    left_sum = max(find_sub_tree_max(node.left), 0)  # recursive, count it in part of O(N) from root
    right_sum = max(find_sub_tree_max(node.right), 0)  # recursive, count it in part of O(N) from root
    current_sum = node.val + left_sum + right_sum  # O(1)
    max_sum = max(max_sum, current_sum)  # O(1)
    return node.val + max(left_sum, right_sum)  # O(1)
def maxPathSum(root):
    if not root:
        return 0
    find_sub_tree_max(root)  # O(N)
    return max_sum

This is a tough problem. To me, there are several things to make sure we understand:

1. how to traverse through the tree
2. what to return when seeing null nodes (0 if null)
3. what to return when seeing negative numbers (max of 0 or the negative num, which is 0)
4. what to return when seeing positive numbers (sum of the nodes)
5. how and what to pass to upper level of the tree (remember we cannot pass the node.val + left.val + right.val up even if it returns the largest sum)

This is a great interview question. It tests interviewers’ ability to traverse a tree, check for max at every level, and to deal with different scenarios. I recommend doing more problems like this.

That’s it! Another problem down.

Buy my a coffee: https://www.buymeacoffee.com/jonathanckz