Recursion

Recursion Hijacking

Lesson

Sometimes you can solve a complicated problem by "hijacking" a very simple recursion. Here's an example.

Problem: Given the root node of a binary tree, return the largest possible sum in any subtree.

A "subtree" is defined as a node in the original tree, and all of its descendants.

Example:

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

Explanation: The right subtree has the largest sum of 1+1+1 = 3. The entire tree has smaller sum of 1+1+1+1+1+1-8 = -2. The other subtrees also have smaller sums.

First Few Test Cases:

1. Recursion

To solve this problem, you would normally look for a recursion involving the maximum sum in the entire tree maxSum(root). But it turns out it's really hard to make this recursive. See the spoiler below for details.

A better way to solve this problem is to use "hijacking". To use "hijacking", you always need to find a simple recursion related to the problem you're solving.

In this problem, we're asked to find the maximum sum at any possible subtree. This means we definitely need to find the sum at every subtree, treeSum(root). We might as well right a recursion for this, since we know we need to do something with it eventually. The sum is equal to the value of the root node, plus the sum of the left tree, plus the sum of the right tree. Here's the recursion for treeSum:

This equation is recursive, which means it calls itself on literally every node in the tree, and finds its sum. This gives us a way to find the largest sum in the tree - we can stick in a few lines of code into the function keep track of the largest sum we see, like this:

To recap, we found a simple function treeSum. We then "hijacked" the function to keep track of the largest sum in the tree.

2. Base case

The recursion calls itself on deeper nodes in the tree. It should stop when it gets to a null node, in which case the sum is 0.

3. Code

To code this up, just combine the recursion and the base case. You have to keep track of the largest sum you see using a global variable, and we'll call it maxSum. We'll initialize it to negative infinity so that it gets overwritten by any new value at first. Here's the code:

We had to use the nonlocal keyword to access the variable inside of the function - see here for more details.

Time Complexity O(n)O(n)

Space Complexity O(n)O(n). treeSum calls itself until it reaches a null node, so it might get nn calls deep (the tree might be a flat line). This means the Call Stack might grow up to size nn.

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