Using Recursion - DeriveIt

1. Recursion

Step 1 is to find a recursive equation.

In this problem, we're asked to find the the number of nodes in a tree, which we'll call numNodes(root). We want to find a Recursive equation for this, which just means we want an equation that has numNodes on both sides of it. It should look something like this:

How do we find this equation? In other words, what is numNodes(root) equal to?

When you're coming up with any recursion, you should think "locally" near the original problem. Here, the original problem is on the root node, so we should think about the nodes root.left and root.right. Here's a visual of this:

From this image, it's pretty obvious that the number of nodes in the tree is just equal to the number of nodes in the left tree, plus the number of nodes in the right tree, plus the 1 root node. This is our recursive equation - the two sides of it are equal, the same way that 1 + 1 = 2.

Typically, you should write the recursion in your code editor and discuss it with your interviewer.

2. Base case

Step 2 is to find when the recursive equation stops working. This is called the "base case".

The recursive equation here stops working if we call a null node, numNodes(None). This is because the recursion uses None.left and None.right which throws an error. We can't use the recursion to find numNodes(None), so we need to manually set what this value is equal to. The number of nodes at a null node is just 0.

3. Code

Step 3 is to code up the solution.

To do this, you should write a function that always returns what numNodes is equal to. That way it's guaranteed to be correct. numNodes is always equal to the recursion, unless we're in the base case in which case it's equal to 0. Here's the full code:

Time Complexity $O(n)$, where $n$ is the number of nodes in the tree. The recursion does roughly 1 operation on every node in the tree. This means it takes $n \cdot O(1)$ time, which is the same as $O(n)$ time.

Space Complexity $O(n)$. For now, you don't need to know where this comes from - we'll go over the full details in the next lesson "Call Stack". Just know the computer needs some memory to keep track of the function calls it's making.