Recursion and Binary Search Trees in Javascript

Recursion

Recursion is the process in which a function calls itself directly or indirectly. A recursive function is a function that calls itself during its execution.

A simple example of a recursive function:

const factorial = (n) => {
    if (n === 1) {
      return 1
    }
    else {
      return n * factorial(n-1)
    }
}

Every recursive function needs to have the simplest solution provided for the base case.

if (n === 1) {
      return 1
}

The solution to the bigger problems are shown in smaller problems.

else {
      return n * factorial(n-1)
}

As you can see, the base case for getting the factorial of n would be 1 and the bigger problems have a recursive call of the factorial recursive method until n is equal to 1.

Let’s show what this recursive call looks like:

const factorial = (n) => {
    if (n === 1) {
      console.log("n " + n);
      return 1
    }
    else {
      console.log("n " + n);
      return n * factorial(n-1)
    }
}
console.log(factorial(5));
console.log(factorial(1));

Output:

n: 5
n: 4
n: 3
n: 2
n: 1
120
n: 1
1

factorial(5) recursively calls factorial(n-1) until it reaches 1 and factorial(1) hits the base case and immediately returns 1.

Now that we have completed a simple example, let’s look at practical applications used with the Binary Search Tree data structure.

Binary Search Tree

A Binary Search Tree is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.

BSTs get an average case of O(log n) on gets, adds, and deletes, but they can have a worst case of O(n) if you add a sorted list (like [1, 2, 3, 4, 5) to a BST.

1
 \
  2
   \
    3
     \
      4
       \
        5

Let’s define a BST that looks like this graphic:

const tree = {
    "value": 8,
    "left": {
        "value": 3,
        "left": {
            "value": 1,
            "left": null,
            "right": null
        },
        "right": {
            "value": 6,
            "left": {
                "value": 4,
                "left": null,
                "right": null
            },
            "right": {
                "value": 7,
                "left": null,
                "right": null
            }
        }
    },
    "right": {
        "value": 10,
        "left": null,
        "right": {
            "value": 14,
            "left": {
                "value": 13,
                "left": null,
                "right": null
            },
            "right": null
        }
    }
}

Depth-first Traversal

Depth-first traversal has the deepest node of the BST visited and then backtracks to its parent node if no sibling of that node exist. There are three types of depth-first traversal.

• Preorder traversal — you process the node, then recursively call the method on the left subtree and then the right subtree.
• Inorder traversal — you first recursively call the method on the left tree, then process the node, and then call the method on the right tree.
• Postorder traversal — you recursively call the method on the left subtree, then the left subtree, then you process the node.

How it looks in Javascript:

const preorderTraverse = (node, array) => {
  if (!node) return array;
  array.push(node.value);
  array = preorderTraverse(node.left, array);
  array = preorderTraverse(node.right, array);
  return array;
};
const inorderTraverse = (node, array) => {
  if (!node) return array;
  array = inorderTraverse(node.left, array);
  array.push(node.value);
  array = inorderTraverse(node.right, array);
  return array;
};
const postorderTraverse = (node, array) => {
  if (!node) return array;
  array = postorderTraverse(node.left, array);
  array = postorderTraverse(node.right, array);
  array.push(node.value);
  return array;
};
console.log(preorderTraverse(tree, []));
console.log(inorderTraverse(tree, []));
console.log(postorderTraverse(tree, []));

Output:

// Preorder
[8, 3, 1, 6, 4, 7, 10, 14, 13]
// Inorder
[1, 3, 5, 6, 7, 8, 10, 13, 14]
// Postorder
[1, 4, 7, 6, 3, 13, 14, 10, 8]

The base case in these recursive methods is if (!node) return array; and the left and right branches of each node are recursively called with array = inorderTraverse(node.left, array); and array = inorderTraverse(node.right, array);. Recursion makes traversing the BST much easier than doing it iteratively.

Other Recursion Examples with BSTs:

const minNode = (node) => {
   if(!node){
      return 0;
   }
   if(node.left){
     return minNode(node.left)
  }
  return node.value
}
const maxNode = (node) => {
   if(!node){
     return 0;
  }
  if(node.right){
     return maxNode(node.right)
  }
  return node.value;
}
const contains = (node, value) => {
  if (!node) {
    return false
  }
  if (node.value === value) {
    return true
  }
  else if (value < node.value) {
    return contains(node.left, value)
  }
  else {
    return contains(node.right, value)
  }
}
console.log(minNode(tree));
console.log(maxNode(tree));
console.log(contains(tree, 10));

Output:

1
14
true
false

Thanks for reading!