Binary Tree Maximum Path Sum

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.
Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.
  • The number of nodes in the tree is in the range [1, 3 * 104].
  • -1000 <= Node.val <= 1000

Recursion

First of all, let’s simplify the problem and implement a function max_gain(node) which takes a node as an argument and computes a maximum contribution that this node and one/zero of its subtrees could add.

  • Initiate max_sum as the smallest possible integer and call max_gain(node = root).
  • Implement max_gain(node) with a check to continue the old path/to start a new path:
  • Base case: if the node is null, the max gain is 0.
  • Call max_gain recursively for the node children to computing max gain from the left and right subtrees : left_gain = max(max_gain(node.left), 0) and
    right_gain = max(max_gain(node.right), 0).
  • Now check to continue the old path or to start a new path. To start a new path would cost price_newpath = node.val + left_gain + right_gain. Update max_sum if it's better to start a new path.
  • For the recursion return the max gain the node and one/zero of its subtrees could add to the current path : node.val + max(left_gain, right_gain).
  • Time complexity: O(N), where N is a number of nodes, since we visit each node not more than 2 times.
  • Space complexity: O(H), where H is a tree height, to keep the recursion stack.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jaydeep

Jaydeep

Full Stack Programmer, love to solve problem’s during free time.