Recursion
Advanced Recursion
Sometimes you can solve a complicated problem by "hijacking" a very simple recursion. Here's an example.
Largest Subtree Sum
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:
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.
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". Hijacking is when you find a simple recursion to something related to the problem, and stick some lines of code in it or "hijack" it to solve the original problem.
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 write 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.
