Solve A Problem Recursively or Iteratively

In this article, we demonstrate two ways of solving problems by using one of the LeetCode practice:

Maximum Binary Tree — LeetCode

Example output

Recursion: Is used when the same procedure can be repeatedly invoked during a process.

If we imagine the process with human thinking, by jumping out of the scale of deduction of how computer is doing it -

• We first pick the maximum of the array, 6
• Then we get the left part beside the maximum, [3,2,1]
• Meanwhile, we get the right part beside the maximum, [0,5]

We find out we need to do the same three-step procedure to left array [3,2,1], and the right array [0,5], we then are sure — that a recursion can be used for this problem.

How to create a recursive function for this problem?

• A base case: so that we can return the result and terminate the process. For example, for an array of length 3, [1,3,2]

var nums = [1,3,2]
var max = Math.max(...nums) // 3
var maxIndex = nums.indexOf(max) // 1
var left = nums.slice(0, maxIndex) // [1]
var right = nums.slice(maxIndex+1, nums.length) // [2]
var res = new TreeNode()
res.val = max
return res

• A recursive case: so that we can break the large problem down to smaller pieces. Therefore, we get:

var constructMaximumBinaryTree = function(nums) {
    var max = Math.max(...nums)
    var maxIndex = nums.indexOf(max)
    var left = nums.slice(0,maxIndex)
    var right = nums.slice(maxIndex+1,nums.length)
    var res = new TreeNode() 
    res.val = max
    if(left.length!==0){
       res.left = constructMaximumBinaryTree(left) //recursively
    }
    if(right.length!==0){
       res.right = constructMaximumBinaryTree(right) //recursively
    }
    return res
};

Iteration: A repetition of a process. Simply speaking, if we have a jar of candy, we pick out each of them one by one, to have a taste.

If we imagine the process with human thinking, by jumping out of the scale of deduction of how computer is doing it -

• We first look at the first element of the array, 3
• We then take a look at the second element of the array, 2. As 2 is smaller than 2, therefore, we put 2 as the right node of the root 3.
• We then take a look at the third element of the array, 1. As 1 is smaller than 2, therefore, we put 1 as the right node of 2.
• We then take a look at the fourth element of the array, 6. As it is larger than the root 3, we create a new root 6 and put 3 as its left leaf.
• …(we take a loot at every elements and insert them to the right place of the tree, and return the tree if we have tasted all of the candy)

The key point is we need to take care of every possible case.

Take another LeetCode Practice as an example:

Binary Tree Inorder Traversal - LeetCode

function inorderTraversal(root) {
  const stack = [];
  const res = [];
while (root || stack.length) {
    if (root) {
      stack.push(root);
      root = root.left;
    } else {
      root = stack.pop();
      res.push(root.val);
      root = root.right;
    }
  }
return res;
}
var minDiffInBST = function(root) {
    var pre = null
    var stack = []
    var min = Infinity
    while (root || stack.length){
       if (root){
           stack.push(root)
           root = root.left
       } else {
           root = stack.pop()
           if (pre){
               min = Math.min(min, Math.abs(pre.val-root.val))
           }
           pre = root  
           root = root.right
       }
    }
    return min
};

Using iteration makes the problem a lot simpler.