Leetcode: Maximum Depth of a Binary Tree

Drawbacks of Recursive Solutions

Published in

The Startup

4 min readJan 16, 2021

When it comes to practicing data structures and algorithms, I often find myself avoiding recursion. Recursion is not my favorite and it's definitely not a strong point. But we have to practice to get better, so I’ve been doing just that.

Recursion is a repetitive process in which a function calls itself.

In recursion, you will see the function calling itself inside the function. To write a recursive solution to a problem, you need these two steps:

Design the base case that will stop the function from calling itself
Design the procedure where the function will call itself (possibly with modified arguments)

After doing a few examples it starts to make sense. Let’s look at the following problem and see how recursion could be used.

Problem:

I chose the Leetcode problem: Maximum Depth of Binary Tree. Given the root of a binary tree, return its max depth where max depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example:

Output: 3

Iterative Solution:

I had already solved this problem before using a DFS implementation. The code was as follows:

var maxDepth = function(root) {
  if (!root) return 0
  let stack = [{ node: root, depth: 1 }]
  let depth = 0
  while (stack.length) {
    curr=stack.pop()
    currNode = curr.node
    if (currNode.left) {
      stack.push({ node: currNode.left, depth: curr.depth + 1 })
    }
    if (currNode.right) {
      stack.push({ node: currNode.right, depth: curr.depth + 1 })
    }
    if (curr.depth > depth) depth = curr.depth
  }
  return depth
};

Recursive Solution:

But this problem can be solved much more eloquently using recursion. Look at the following solution:

var maxDepth = function(root) {
    if(!root) return 0
    return 1 + Math.max(depth(root.left), depth(root.right))
  }

Wow, that's much less code than before! This solution makes use of recursion. Let's go through the steps I outlined above.

Design the base case: This will occur when the root passed into the function does not exist. In this case, we will simply return 0.
Design the procedure: If the root does exist, the max depth will be the max depth of the left side or the right side of the tree, depending on which is larger, plus 1 (to account for the current node).

The Problem With Recursion:

The recursive solution is much shorter than the iterative one I had before, but if you are struggling with recursion, no worries! Recursion is not all that special. In fact, instead of learning how to implement recursion let's learn a few reasons why recursion isn't that important after all.

Iteration Works Just As Well

Just as I showed in the problem above, you don't need recursion to solve a problem. Both iteration and recursion are repetitive processes and they will both repeat a certain procedure until some condition is met. So if you don't want to use recursion, an iterative solution exists instead.

A language can be considered Turing complete (can do all the things), even by not having recursion or by not having iteration. This means iterations can do anything recursion can and vice versa.

If you were curious about languages without iteration: Haskell and Scheme. Also, Fortran used to not have recursion.

Recursion Uses More Memory

Recursion uses a stack data structure to work. Let's go through the steps that occur when a function is called:

Space is allocated on a stack for the function’s arguments and variables
The allocated space is used by the function as the function code executes
The stack is reset once the code has finished executing

Now here is the issue with recursion. Since the function calls itself before the end, step 3 doesn't happen quite yet. Each time a recursive call is made, more space is allocated on the stack (steps 1 and 2) but the stack will only be cleared (step 3)once the function has completed its final iteration and starts to unwind. Remember, stacks work as a LIFO (Last In, First Out). Thus, a recursive function has a greater space requirement than an iterative one.

The stack grows with each recursive call, and this can lead to intensive memory usage. If it grows too large, it can cause the compiler to run out of memory and cause a stack overflow exception. This is because there is a limit to how many times the compiler will let you call the function before it needs you to be finished. This usually occurs with very large sets of data and will crash your application.. oops.

Recursion Can Be Slow

Depending on the implementation, a recursive solution can have greater time requirements than an iterative one. This is related to the last point, where a recursive solution has to allocate a new stack frame with each call. The additional functional calls and memory allocations slow down the processing time. The answer will only be returned once the stack has been “popped” clean.