Leetcode - Binary Tree Maximum Path Sum

Question

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.

This is atree question.

Idea(s)

• Brute force approach:
  • Solve this question recursively (DFS)
    • Base case is no root → return 0
  • Start at root
    • Check the path of the left and right children of the current node for a new max
    • Check left and right subtrees for the max path if they don’t split (if both children are negative), or if we split left vs right (max of left and right subtree)
  • We would pass the root + the max of the left or right return values to its parent
  • The return value for every node is the max path without splitting
• Process from idea
  • Calculate leftMax and rightMax by recursively calling dfs on left and right subtrees and taking the max with 0 to filter out negative values
  • Compute max path sum by taking the max of the current result, and the root with splits allowed
  • Return the current node value + the value of the larger subtree (we don’t want to return the max path sum with splits allowed because that does not create a path, we previously just check for that case to update the result if required)

O(n) time complexity and O(log(n)) space complexity for a balanced tree solution

Solution