Recursion

Max Node to Node Sum

Given the root node of a binary tree root, return the largest sum that goes from one node in the tree to another node. The path must be continuous and must include at least 1 node.

Example 1:

image
=> returns 15 = 6+4+2+3\notag \large \texttt{=> returns 15 = 6+4+2+3}

Example 2:

=> returns 2\notag \large \texttt{=> returns 2}

Hint:

First Few Test Cases:

Solution:

To solve this problem, you can compute the maximum path sum through each node, and return the largest sum that you saw at the end.

The max path through a node contains the node's value. It also either contains a path that goes strictly down through the left node, or through the right node, or it contains both these paths, or neither.

both

left

neither

Here's an equation for this:

When we write maxPathDown, we mean a path strictly downwards, which never splits in two.

1. Recursion

The above equation isn't recursive, so it feels like we're stuck. But it's clear how to compute maxPathDown recursively. The max path downwards, starting at a node, always contains the node's value, and it either contains the path to the left, or the path to the right, or neither. It just can't contain both, because that would make it split in two. Here's the recursion for maxPathDown:

This recursion already computes everything we need in order to compute maxPath. So a clever idea is to "hijack" the recursion to also compute the max path going through this node. We can do this by just sticking in a line of code:

2. Base case

Eventually the recursion gets to a node that's null. The maximum path through a null node is 0.

3. Code

Combining the recursion and base case, and keeping track of the largest maxPath we see, we get this code:

Time Complexity O(n)O(n). We visit every node once.

Space Complexity O(n)O(n). The recursion might get n nodes deep, so the Call Stack grows to size O(n).

Mark as Completed:
Submits:
maximumPathSum
Imports:
TreeNode
Test your code to get an output here!
maximumPathSum(
)
Test your code to get an output here!