Binary Search Tree in Javascript

A closure in javascript is a combination of a function bundled together (enclosed) with references to its surrounding state (the lexical environment).

In other words, a closure gives you access to an outer function’s scope from an inner function. In JavaScript, closures are created every time a function is created, at function creation time.

Example

function outerFunc(outerVar) {
  return function innerFunc(innerVar) {
    console.log(outerVar);
    console.log(innerVar);
  };
}


const innerFn = outerFunc("outer");
innerFn("inner");



Output :

outer
inner

In the above example, the innerFunction has access to outerVar even though it was called at a different point in time. This is because javascript allows accessing the lexical context of the outer function inside the inner function ( not vice versa ). This constitutes the concept of closures. It is a pretty simple concept but many people have tagged this as an advanced concept in javascript.

Practical example

Closures are used when making HTTP requests (callbacks) to access outer scoped variables.

let response = null;
let error = null;


fetch("https://reqres.in/api/users")
  .then((response) => {
    response = response.data;
  })
  .catch((error) => {
    error = error.message;
  });

In the above example, the variables response and error are declared outside the callback function which is inside -> .then( callback ). But still we are able to set the values inside the callback. This is because of closures. Outer lexical context is available inside the inner function.

PROBLEM

Implement a binary search tree ( BST ) using Javascript closures and implement the following methods.

// A method to place a node in the correct position in BST
add();

// A method to find minimum node in the BST
findMin();

// A method to find maximum node in the BST
findMax();

// A method to fing the tree height.
findTreeHeight();

// A method to find maximum depth of the tree
findMaximumDepth();

// A method to find minimum depth of the tree
findMinimumDepth();

SOLUTION

In a binary search tree, all the nodes in the left subtree are lesser than or equal to all the nodes in the right subtree. ( LST <= RST )

Javascript code

function BST() {
  let root = null;


  // Helper method
  let findNodeHeight = (node) => {
    return (function findHeight(node) {
      if (!node) {
        return -1;
      } else {
        return Math.max(findHeight(node.left), findHeight(node.right)) + 1;
      }
    })(node);
  };


  return {

    add: (data) => {
      const node = new Node(data);
      if (!root) {
        root = node;
        return;
      }

      (function insert(node) {
        if (data < node.data) {
          if (!node.left) {
            node.left = new Node(data);
            return;
          } else {
            insert(node.left);
          }
        } else {
          if (!node.right) {
            node.right = new Node(data);
            return;
          } else {
            insert(node.right);
          }
        }
      })(root);
    },

    findMin: () => {
      let currentNode = root;
      while (currentNode.left) {
        currentNode = currentNode.left;
      }
      return currentNode.data;
    },

    findMax: () => {
      let currentNode = root;
      while (currentNode.right) {
        currentNode = currentNode.right;
      }
      return currentNode.data;
    },

    findTreeHeight: () => {
      return findNodeHeight(root);
    },

    findMaximumDepth: () => {
      return findTreeHeightFn();
    },

    findMinimumDepth: () => {
      return (function findMinDepth(node) {
        if (!node) {
          return 0;
        }
        if (!node.left && !node.right) {
          return 1;
        }
        if (!node.left) {
          return findMinDepth(node.right) + 1;
        }
        if (!node.right) {
          return findMinDepth(node.left) + 1;
        }

        return Math.min(findMinDepth(node.left), findMinDepth(node.right)) + 1;
      })(root);
    },
  };
}

Now we can construct the BST

let bst = new BST();
bst.add(10);
bst.add(20);
bst.add(5);
bst.add(15);
bst.add(3);

bst.add(30);