Recursion vs. Iteration in a binary tree
Tags: recursion, iteration, javascript
Published: 2020-08-21 17:22:16

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](https://leetcode.com/problems/symmetric-tree) 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:
![symmetric tree](https://dev-to-uploads.s3.amazonaws.com/i/26rekuvi2bnn62kjyaxb.png)
but this tree is not:
![not a symmetric tree](https://dev-to-uploads.s3.amazonaws.com/i/abx9gt68vk8eqygxdxm8.png)

The Tree class is already defined for us, and the `left`, `right`, and `val` properties are available to use:
```js
 //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:
```js
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:

```js
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!