Jobs

Interviews

Discussions

Binary Tree Maximum Path Sum

Hard

Binary Tree Maximum Path Sum

Hard

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can node values be negative, zero, or only positive?
What is the range of possible integer values for the nodes in the tree, and should I be concerned about integer overflow during summation?
Is an empty tree a possible input, and if so, what should the return value be?
Could the tree consist of just a single node, and if so, what would the expected output be?
By 'path,' do you mean a simple path (no cycles), and is it acceptable for the path to consist of a single node?

Brute Force Solution

Approach

The brute force strategy for finding the maximum path sum in a binary tree is to explore every possible path. We calculate the sum of each path and then compare these sums to find the largest one. This involves generating all potential paths and checking each one.

Here's how the algorithm would work step-by-step:

Consider every single node in the tree as a potential starting point for a path.
From each starting node, explore all possible paths downwards. A path can go down to the left child, the right child, or both.
For each path you find, calculate the sum of all the node values along that path.
Keep track of the largest sum you've seen so far. Every time you calculate a path sum, compare it to the largest sum you've stored.
If the current path sum is larger than the largest sum stored, replace the stored value with the current path sum.
After exploring all possible paths from every node in the tree, the largest sum you've stored will be the maximum path sum for the entire tree.

Code Implementation

def max_path_sum_brute_force(root):
    maximum_sum = float('-inf')

    def all_paths_from_node(node):
        if not node:
            return []

        # Base case: leaf node
        if not node.left and not node.right:
            return [[node.val]]

        left_paths = all_paths_from_node(node.left)
        right_paths = all_paths_from_node(node.right)

        all_paths = [[node.val] + path for path in left_paths] + \
                    [[node.val] + path for path in right_paths]

        # Add the node itself as a path
        all_paths.append([node.val])
        return all_paths

    def calculate_path_sum(path):
        return sum(path)

    all_possible_paths = []
    
    def collect_paths(node):
        nonlocal all_possible_paths
        if node:
            all_possible_paths.extend(all_paths_from_node(node))
            collect_paths(node.left)
            collect_paths(node.right)

    collect_paths(root)
    
    #Iterate through each path to calculate it's total sum
    for path in all_possible_paths:
        current_path_sum = calculate_path_sum(path)

        #Store the maximum path sum found so far.
        maximum_sum = max(maximum_sum, current_path_sum)

    return maximum_sum

Big(O) Analysis

Time Complexity

O(n²) – The brute force approach considers each of the n nodes as a starting point. From each starting node, in the worst case, we explore a path that traverses a significant portion of the tree downwards. The number of paths originating from a single node could potentially involve visiting a substantial fraction, perhaps up to n, of the remaining nodes. Considering all n nodes as starting points, and for each exploring roughly n nodes in the worst-case scenarios when searching for maximum paths results in O(n * n) = O(n²) time complexity.

Space Complexity

O(N) – The brute force approach described explores all possible paths in the binary tree using recursion. In the worst-case scenario (a skewed tree), the recursion depth can be equal to the number of nodes (N) in the tree. Each recursive call adds a new frame to the call stack, which stores local variables and the return address. Therefore, the maximum space used by the call stack is proportional to the height of the tree, which is N in the worst case, resulting in O(N) space complexity due to the recursion depth. No other significant auxiliary data structures are used.

Optimal Solution

Approach

The core idea is to traverse the tree and calculate the maximum path sum in a bottom-up manner. Each node computes the best path sum that includes itself and possibly one of its children. The global maximum path sum is updated during this process.

Here's how the algorithm would work step-by-step:

Imagine you're exploring the tree, starting from the very bottom.
At each point, think about the best possible 'line' you can make that goes through that point. This line can either be just the point itself, the point plus its left child, the point plus its right child, or the point plus both children forming a 'V' shape.
Keep track of the absolute best 'line' you've found so far, anywhere in the tree.
When you move up to the point above, decide the best path that includes going to the parent. We have to pick either the left or the right child's contribution, so we pick the largest one, or just the point if both the child paths contribute negatively.
Update the 'absolute best line' we've seen if the new point or 'V' shape going through the new point is larger.
Continue doing this until you've reached the very top.
The 'absolute best line' that you kept track of is your answer.

Code Implementation

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

def max_path_sum(root):
    maximum_path_sum = float('-inf')

    def max_path_sum_recursive(node):
        nonlocal maximum_path_sum
        if not node:
            return 0

        # Recursively calculate the max path sum for the left and right subtrees
        left_max_sum = max(0, max_path_sum_recursive(node.left))
        right_max_sum = max(0, max_path_sum_recursive(node.right))

        # Update the global maximum path sum
        # considering the current node as the root of the path.
        price_newpath = node.val + left_max_sum + right_max_sum
        maximum_path_sum = max(maximum_path_sum, price_newpath)

        # Return the maximum path sum that includes the current node
        # and one of its children. Crucial for connecting to the parent.
        return node.val + max(left_max_sum, right_max_sum)

    max_path_sum_recursive(root)
    # The maximum_path_sum has been updated during recursive calls.
    return maximum_path_sum

Big(O) Analysis

Time Complexity

O(n) – The algorithm performs a single Depth-First Search (DFS) traversal of the binary tree. Each node in the tree is visited exactly once. At each node, a constant amount of work is done: calculating the maximum path sum including the node and updating the global maximum. Therefore, the time complexity is directly proportional to the number of nodes in the tree, which is denoted as 'n'. This single traversal leads to a linear relationship between the number of nodes and the execution time.

Space Complexity

O(H) – The dominant space complexity comes from the recursion depth of the depth-first traversal. In the worst case, the tree is skewed, and the recursion depth equals the height of the tree, H, leading to H stack frames. Each stack frame stores local variables for the current node being processed and the return address. Therefore, the auxiliary space used is proportional to the height of the tree. In the best/average case for a balanced tree the height is log(N) but the question asks for the generic case space complexity analysis so we will consider H which is the height of the tree as our result.

Edge Cases

Case	How to Handle
Null root node	Return negative infinity to not contribute to max sum.
Single node tree	Return the node's value directly.
Tree with all negative values	Handle correctly by selecting the largest (least negative) single node value as the maximum path sum.
Tree with all zero values	Handle correctly; the maximum path sum will be zero.
Tree with extremely large positive values potentially causing integer overflow	Use long data type to prevent potential integer overflow issues when calculating path sums.
Skewed tree (all nodes on one side)	Recursively traverse the skewed tree correctly and update the maximum path sum.
Tree with a long path of small positive values and a single large negative value	The algorithm should correctly identify if including the negative value reduces the overall maximum sum or not.
Deeply nested tree potentially leading to stack overflow due to excessive recursion	Consider alternative iterative approach to manage call stack if necessary.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can node values be negative, zero, or only positive?
What is the range of possible integer values for the nodes in the tree, and should I be concerned about integer overflow during summation?
Is an empty tree a possible input, and if so, what should the return value be?
Could the tree consist of just a single node, and if so, what would the expected output be?
By 'path,' do you mean a simple path (no cycles), and is it acceptable for the path to consist of a single node?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider every single node in the tree as a potential starting point for a path.
From each starting node, explore all possible paths downwards. A path can go down to the left child, the right child, or both.
For each path you find, calculate the sum of all the node values along that path.
Keep track of the largest sum you've seen so far. Every time you calculate a path sum, compare it to the largest sum you've stored.
If the current path sum is larger than the largest sum stored, replace the stored value with the current path sum.
After exploring all possible paths from every node in the tree, the largest sum you've stored will be the maximum path sum for the entire tree.

Code Implementation

def max_path_sum_brute_force(root):
    maximum_sum = float('-inf')

    def all_paths_from_node(node):
        if not node:
            return []

        # Base case: leaf node
        if not node.left and not node.right:
            return [[node.val]]

        left_paths = all_paths_from_node(node.left)
        right_paths = all_paths_from_node(node.right)

        all_paths = [[node.val] + path for path in left_paths] + \
                    [[node.val] + path for path in right_paths]

        # Add the node itself as a path
        all_paths.append([node.val])
        return all_paths

    def calculate_path_sum(path):
        return sum(path)

    all_possible_paths = []
    
    def collect_paths(node):
        nonlocal all_possible_paths
        if node:
            all_possible_paths.extend(all_paths_from_node(node))
            collect_paths(node.left)
            collect_paths(node.right)

    collect_paths(root)
    
    #Iterate through each path to calculate it's total sum
    for path in all_possible_paths:
        current_path_sum = calculate_path_sum(path)

        #Store the maximum path sum found so far.
        maximum_sum = max(maximum_sum, current_path_sum)

    return maximum_sum

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you're exploring the tree, starting from the very bottom.
At each point, think about the best possible 'line' you can make that goes through that point. This line can either be just the point itself, the point plus its left child, the point plus its right child, or the point plus both children forming a 'V' shape.
Keep track of the absolute best 'line' you've found so far, anywhere in the tree.
When you move up to the point above, decide the best path that includes going to the parent. We have to pick either the left or the right child's contribution, so we pick the largest one, or just the point if both the child paths contribute negatively.
Update the 'absolute best line' we've seen if the new point or 'V' shape going through the new point is larger.
Continue doing this until you've reached the very top.
The 'absolute best line' that you kept track of is your answer.

Code Implementation

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

def max_path_sum(root):
    maximum_path_sum = float('-inf')

    def max_path_sum_recursive(node):
        nonlocal maximum_path_sum
        if not node:
            return 0

        # Recursively calculate the max path sum for the left and right subtrees
        left_max_sum = max(0, max_path_sum_recursive(node.left))
        right_max_sum = max(0, max_path_sum_recursive(node.right))

        # Update the global maximum path sum
        # considering the current node as the root of the path.
        price_newpath = node.val + left_max_sum + right_max_sum
        maximum_path_sum = max(maximum_path_sum, price_newpath)

        # Return the maximum path sum that includes the current node
        # and one of its children. Crucial for connecting to the parent.
        return node.val + max(left_max_sum, right_max_sum)

    max_path_sum_recursive(root)
    # The maximum_path_sum has been updated during recursive calls.
    return maximum_path_sum

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null root node	Return negative infinity to not contribute to max sum.
Single node tree	Return the node's value directly.
Tree with all negative values	Handle correctly by selecting the largest (least negative) single node value as the maximum path sum.
Tree with all zero values	Handle correctly; the maximum path sum will be zero.
Tree with extremely large positive values potentially causing integer overflow	Use long data type to prevent potential integer overflow issues when calculating path sums.
Skewed tree (all nodes on one side)	Recursively traverse the skewed tree correctly and update the maximum path sum.
Tree with a long path of small positive values and a single large negative value	The algorithm should correctly identify if including the negative value reduces the overall maximum sum or not.
Deeply nested tree potentially leading to stack overflow due to excessive recursion	Consider alternative iterative approach to manage call stack if necessary.