Recursion vs. Iteration in a binary tree

When approaching an algorithm, often you have to choose between a recursive approach or an iterative approach. Although some problems or languages naturally favor one approach over another, really they can be used interchangeably. It's all a matter of understanding how to frame the problem.

Both recursion and iteration run a chunk of code until a stopping condition is reached. With recursion, you repeatedly call the same function until that stopping condition, and then return values up the call stack. With iteration, rather than building a call stack you might be storing data in a particular data structure, often a stack or queue, and then running a loop that utilizes that data until the stopping condition is met.

To make these ideas more concrete, here are two solutions to check if a binary tree is symmetric - one recursive and one iterative. This problem is from Leetcode if you want to submit your own solution there! Binary trees are very conducive to recursive solutions, since each piece of a binary tree is just another binary tree. But iterative approaches can be used as well, in this case by utilizing a queue.

Here's the basic problem: a binary search tree is symmetric if it is a mirror image of itself down the center. So this tree is symmetric:

but this tree is not:

The Tree class is already defined for us, and the left, right, and val properties are available to use:

 //Definition for a binary tree node.
 function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
 }

Given the root node of the tree, the problem is to write an algorithm to check if that tree is symmetric. Whichever approach is used, the solution needs to check that the left branch of the left branch equals the right branch of the right branch (left.left === right.right) and the right branch of the left branch equals the left branch of the right branch (left.right === right.left). If this condition holds for every subtree, where left and right are the mirror nodes of each other, than the tree is symmetric.

First let's look at the recursive solution. In this solution, a sub-function takes left and right as arguments and compares those values, and then calls itself on the left and right children of those nodes. Here's the full implementation:

const isSymmetric = root => {
  function compare(left, right) {
    if (left === null && right === null) {
      return true
    } else if (left === null || right === null || left.val !== right.val) {
      return false
    } else {
      return compare(left.left, right.right) && compare(left.right, right.left)
    }
  }
  if (root === null) {
    return true
  }
  return compare(root.left, root.right)
};

Before calling compare at all, we check if the root is even a tree. If it's not, there's no work to do. But assuming if is, we start off our recursive calls with root.left and root.right. First we check if both left and right are null, since we can't call .left or .right if those are not actually TreeNodes! This is one of our stopping conditions, and matching null values in the left and right position meet the criteria for a symmetric tree, so true is returned up the call stack. In the next line, the conditions that violate a symmetric tree are checked. Again, since .left and .right cannot be called on a null value, those cases are checked first. If the values do not match, the tree is not symmetric and false is returned up the call stack. Those are the two stopping conditions. Finally, if neither of those conditions are met, the compare function is recursively called down each branch of the tree. The && ensures that both sides must return true for the outer function call to return true - if any of the inner calls resolve to false, that will be passed up the call stack and the function with ultimately return false.

It's important to remember that in a recursive solution the inner return values must be passed up the call stack! There are no implicit returns in JavaScript, so the recursive calls of compare must be explicitly returned as well. The use of return is one of the key differences between the recursive and iterative solution - let's look at the iterative solution now:

const isSymmetric = root => {
  if (root === null) {
    return true
  }
  let queue = []
  queue.push(root.left, root.right)

  while (queue.length > 0) {
    let left = queue.shift()
    let right = queue.shift()
    if (left === null && right === null) {
      continue
    } else if (left === null || right === null || left.val !== right.val) {
      return false
    } else {
      queue.push(left.left, right.right, left.right, right.left)
    }
  }
  return true
}

Again, the first step is to confirm we actually have a TreeNode to start. If we do, we initiate a queue with root.left and root.right. From there, the code logic is nearly identical to the recursive solution. The big difference is that rather than building a call stack, we are adding nodes to our queue and running the while loop until the queue is empty. Another important difference is the use of return. In the first condition left === null && right === null, rather than stop the loop and return true, what we want is to continue checking other nodes. Returning true there would break out of the loop and return true from the isSymmetric function immediately, since we aren't buried in a call stack. Knowing where to use return and what function it is ending is key to building iterative vs recursive solutions. On the other hand, in the next condition, if a false condition is found, we're done! We do want to end the while loop and immediately return false. Only if no false condition is ever found do we hit the last line and return true.

I hope this provides a concrete example of moving between recursion and iteration. For me, understanding what return is doing and the different stopping conditions is key to moving between these two approaches.

Thanks for reading!