Katkat
Back

Compute sums and maximum path in a tree

UberSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to perform post-order tree traversals to calculate subtree metrics and solve optimization problems involving paths that can span across parent-child boundaries.

Maximum Path Sum in a Binary Tree

Given the root of a binary tree, where each node contains an integer value, find the maximum path sum of any non-empty path. A path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to pass through the root.

Function Signature

def max_path_sum(root: Optional[TreeNode]) -> int:

Constraints

  • The number of nodes in the tree is in the range [1, 3 * 10^4].
  • Node values are in the range [-1000, 1000].

Examples

Example 1:

  • Input: root = [1, 2, 3]
  • Output: 6
  • Explanation: The path is 2 -> 1 -> 3 with sum 2 + 1 + 3 = 6.

Example 2:

  • Input: root = [-10, 9, 20, None, None, 15, 7]
  • Output: 42
  • Explanation: The path is 15 -> 20 -> 7 with sum 15 + 20 + 7 = 42.

Edge Cases

  • A tree containing only negative values: the result should be the maximum single node value.
  • A tree with a single node.
  • A tree with unbalanced branches (e.g., heavily skewed to the left or right).

Hints

Hint 1

For any node, the maximum path passing through it as the highest point is the node's value plus the maximum path sum of its left child (if positive) and its right child (if positive).

Hint 2

You need a recursive helper function that returns the maximum path sum starting from a node and going down into its subtree, while simultaneously updating a global maximum variable with the path that uses the node as a bridge.

Hint 3

Be careful to ignore negative contributions from child subtrees, as a path is not required to include a branch if that branch would decrease the total sum.

Follow-up questions

  • How would you modify the algorithm if the path must start and end at leaf nodes?
  • What is the time and space complexity of your solution, and can you optimize the space complexity if the tree is highly skewed?
  • If we wanted to print the actual nodes that form this maximum path, what data would you need to track during your recursion?