Count maximum path in binary tree

Question

Given a binary tree, write a function to count the maximum path sum from any node to any node in the tree. A path is defined as any sequence of nodes from one node to another, where each pair of adjacent nodes in the path must be connected by an edge. The function should return the maximum path sum as an integer.

Codemia · Accepted Answer

To solve the problem of finding the maximum path sum in a binary tree, we can utilize a depth-first search (DFS) approach. This is because we need to explore the tree structure, where each node can connect to its left and right children. The optimal solution requires us to calculate the maximum path sum while ensuring that the path can start and end at any node in the tree. The key insight is that for each node, we can compute the maximum path sum that includes that node and extends to its children, allowing us to account for paths that might branch out at nodes.

1. Define a recursive DFS function that returns the maximum path sum that can be obtained from the current node to any of its descendants. This will help us evaluate paths extending downwards.
2. At each node, calculate the maximum contribution from the left and right children.
3. Compute the maximum path sum that includes the current node, which would be the sum of the node's value and the contributions from both children (if they are positive).
4. Track the global maximum path sum as we traverse the tree.
5. The recursive calls will help us explore all possible paths in the tree.

Example: For the tree structure:
```
        1
       / \
      2   3
     / \
    4   5
```
The maximum path would be 4 + 2 + 1 + 3 = 10.

Here is the Python implementation of the solution:
```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.max_sum = float('-inf')

def dfs(node):
            if not node:
                return 0
            left = max(dfs(node.left), 0)
            right = max(dfs(node.right), 0)
            current_path_sum = node.val + left + right
            self.max_sum = max(self.max_sum, current_path_sum)
            return node.val + max(left, right)

dfs(root)
        return self.max_sum
```
This code defines a `TreeNode` class to represent the tree nodes and a `Solution` class with a method to compute the maximum path sum.

The time complexity of this solution is O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once during the DFS traversal. The space complexity is O(h), where h is the height of the tree, due to the recursive call stack. In the worst case of a skewed tree, this could be O(n), but in a balanced tree, it would be O(log n).

1. An empty tree: The function should return a value indicating that no path exists, which could be set to 0 or negative infinity based on problem constraints.
2. A single-node tree: The maximum path sum should be the value of that single node.
3. Trees with all negative values: The maximum path sum should still consider the highest single node value, as paths can include negative sums.
4. Various tree shapes (balanced vs. skewed) should not affect the correctness of the algorithm since it handles all paths uniformly.

Count maximum path in binary tree

Pinterest

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Pinterest Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string