Recursion

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:**

$\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.

This solution is not recommended for an interview since it's nonstandard. "Hijacking" is the standard way to solve this problem, and we talk about it outside of this spoiler.

1. Recursion

Here's the recursion for the largest sum in a tree `maxSum`

:

This recursion isn't 100% complete though, because it uses another function `treeSum`

. Here's what the recursion for *that* looks like:

We have two recursions that we want to compute, which we haven't seen before. There's no problem with this though - we'll just write a function that computes both of these at the same time.

2. Base case

The `maxSum`

recursion will eventually get called on a null node.
If a node is null, it doesn't make sense for it to have a maxSum. In that case, we can set it equal to -infinity so that it gets ignored when we take the maximum, since -infinity is smaller than any other number.

The `treeSum`

recursion will also get called on a null node. It doesn't sense for a null node to have a sum. In that case, we can set the value equal to 0 so that it gets ignored when we add it to the other numbers.

3. Code

To code this up, we just combine the recursion and base case.
Since we have 2 recursions, our function will return both the `treeSum`

and `maxSum`

in a tuple. If you don't do this, the recursion is very inefficient. Here's the code:

Time Complexity $O(n)$.

Space Complexity $O(n)$ from the Call Stack.

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)$

Space Complexity $O(n)$. `treeSum`

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

Mark as Completed: