Trees

binary-search-tree.js

'use strict';

function BinarySearchTree() {
  this.root = null;
}

BinarySearchTree.prototype.insertNode = function (val) {
  var node = {
    data : val, 
    left : null, 
    right : null
  };

  var currentNode;
  
  if (!this.root) {
    this.root = node;
  } else {
    currentNode = this.root;
    while (currentNode) {
      if (val < currentNode.data) {
          if (!currentNode.left) {
            currentNode.left = node;
            break;
          } else {
            currentNode = currentNode.left;
          }
      } else if (val > currentNode.data) {
        if (!currentNode.right) {
          currentNode.right = node;
          break;
        } else {
          currentNode = currentNode.right;
        }
      } else {
        console.log('Ignoring this value as the BST supposed to be a tree containing UNIQUE values');
        break;
      }
    }    
  }
};

var BST = new BinarySearchTree();

BST.insertNode(8);
BST.insertNode(3);
BST.insertNode(10);
BST.insertNode(1);
BST.insertNode(6);
BST.insertNode(14);
BST.insertNode(4);
BST.insertNode(7);
BST.insertNode(13);

console.log(BST);

commonAncestor.js

'use strict';

function commonAncestor(n1, n2) {
  var inOrderTra = inOrder(this);
  var postOrderTra = postOrder(this);

  var i1 = inOrderTra.indexOf(n1);
  var i2 = inOrderTra.indexOf(n2);
  var middleNodes = inOrderTra.splice(i1 + 1, i2);

  var map = middleNodes.map(function(i) {
    return {
      i: postOrderTra.indexOf(i)
    };
  });

  // Find the node with the highest index value
  return Object.keys(map).reduce(function(a, b) {
    return map[a] > map[b] ? a : b;
  });
}

/*
Returns an array containing all the elements in the in-order traversal.
@param {BT} root
*/
function inOrder(root) {
  ...
}

/*
Returns an array containing all the elements in the post-order traversal.
@param {BT} root
*/
function postOrder(root) {
  ...
}

connect-nodes-at-same-level.js

var BST = new BinarySearchTree();

BST.insertNode(8);
BST.insertNode(3);
BST.insertNode(10);
BST.insertNode(1);
BST.insertNode(6);
BST.insertNode(14);
BST.insertNode(4);
BST.insertNode(7);
BST.insertNode(13);


function connectNodesAtSameLevel (BST) {
  var temp, temp2, queue = []
  
  // Initialize roots height
  BST.root.height = 0
  queue.push(BST.root)
  
  while (queue.length) {
    
    // Deque the Queue
    temp = queue.splice(0, 1)[0]
    
    // Set the nextRight for the temp node
    if (queue[0]){
      temp2 = queue[0]
    
      if (temp.height === temp2.height) 
        temp.nextRight = temp2
      else 
        temp.nextRight = undefined      
    }
       
    // Enqueue the Queue
    if (temp.left) {
      queue.push(temp.left)
      // Set relevant height
      temp.left.height = temp.height + 1
    }
    if (temp.right) {
      queue.push(temp.right)
      temp.right.height = temp.height + 1      
    }

  }
}

connectNodesAtSameLevel(BST) 
console.log(BST)

create-min-height-bst.js

'use strict';

function BinarySearchTree() {
  this.root = null;
}

BinarySearchTree.prototype.createMinHeightBST = function (sortedrArr) {

  var middle;
  if (sortedrArr.length === 0) {
    return 0;
  } else if (sortedrArr.length === 1) {
    middle = 0;
  } else {
    middle = Math.floor(sortedrArr.length / 2);
  }
  // http://js-interview.tutorialhorizon.com/2015/10/12/create-a-binary-search-tree-in-javascript/
  this.insertNode(sortedrArr[middle]);

  var leftArr = sortedrArr.slice(0, middle);
  var rightArr = sortedrArr.slice(middle+1, sortedrArr.length);

  this.createMinHeightBST(leftArr);
  this.createMinHeightBST(rightArr);
};

var BST = new BinarySearchTree();
var sortedUniqueArr = [0, 1, 2, 3, 4, 5, 6];

BST.createMinHeightBST(sortedUniqueArr);
console.log(BST);

delete-tree.js

function deleteTree(node) {
    if (node == NULL) return;

    // Delete left, right subtrees
    deleteTree(node.left);
    deleteTree(node.right);

    deleteNode(node);
}

delte-tree-non-recursive.js

function deleteTree (root) {

  let temp = [];

  while (temp) {
    
    let node = temp.pop();

    if (node.left) temp.push(node.left);
    if (node.right) temp.push(node.right);
    
    deleteNode(node);
  }
}

es6-binary-search-tree.js

'use strict';

class BinarySearchTree {

  constructor() {
    this.root = null;
  }

  insertNode(val) {
    var node = {
      data: val,
      left: null,
      right: null
    };

    var currentNode;

    if (!this.root) {
      this.root = node;
    } else {
      currentNode = this.root;
      while (currentNode) {
        if (val < currentNode.data) {
          if (!currentNode.left) {
            currentNode.left = node;
            break;
          } else {
            currentNode = currentNode.left;
          }
        } else if (val > currentNode.data) {
          if (!currentNode.right) {
            currentNode.right = node;
            break;
          } else {
            currentNode = currentNode.right;
          }
        } else {
          console.log('Ignoring this value as the BST supposed to be a tree containing UNIQUE values');
          break;
        }
      }
    }
  }
}

var BST = new BinarySearchTree();

BST.insertNode(8);
BST.insertNode(3);
BST.insertNode(10);
BST.insertNode(1);
BST.insertNode(6);
BST.insertNode(14);
BST.insertNode(4);
BST.insertNode(7);
BST.insertNode(13);

console.log(BST);

es6-bst-traversal.js

'use strict';

class BinarySearchTree {

  constructor() {
    this.root = null;
  }

  preOrderTraversal(root) {

    console.log(root.data);
    if (root.left) {
      this.preOrderTraversal(root.left);
    }
    if (root.right) {
      this.preOrderTraversal(root.right);
    }
  }

  postOrderTraversal(root) {

    if (root.left) {
      this.postOrderTraversal(root.left);
    }
    if (root.right) {
      this.postOrderTraversal(root.right);
    }
    console.log(root.data);

  }

  inOrderTraversal(root) {

    if (root.left) {
      this.inOrderTraversal(root.left);
    }
    console.log(root.data);
    if (root.right) {
      this.inOrderTraversal(root.right);
    }
  }
}

var BST = new BinarySearchTree();

BST.insertNode(8);
BST.insertNode(3);
BST.insertNode(10);
BST.insertNode(1);
BST.insertNode(6);
BST.insertNode(14);
BST.insertNode(4);
BST.insertNode(7);
BST.insertNode(13);

console.log(BST);

in-order-traversal.js

function BinarySearchTree() {
  this.root = null;
}

BinarySearchTree.prototype.inOrderTraversal = function (root) {

  if (root.left) {
    this.inOrderTraversal(root.left);
  } 
  
  console.log(root.data);
    
  if (root.right) {
    this.inOrderTraversal(root.right);
  }
};

// Create a new Balanced Binary Tree as a sample input
// http://js-interview.tutorialhorizon.com/2015/10/12/create-a-binary-search-tree-in-javascript/
var BST = new BinarySearchTree();
BST.insertNode(10);
BST.insertNode(15);
BST.insertNode(5);
BST.insertNode(2);
BST.insertNode(3);
BST.insertNode(12);
BST.insertNode(17);

BST.inOrderTraversal(BST.root); // 2, 3, 5, 10, 12, 15, 17

inOrderSuccessor.js

'use strict';

function inOrderSuccessor(node) {
  if (!node) {
    return null;
  }

  if (node.right) {
    return leftMostChild(node.right);
  } else {
    var currentNode = node;
    // Assuming each node has a reference to its parent
    var parentNode = currentNode.parent;

    // Go up until we find deepest ancestor for which node would be in left sub tree
    while (parentNode && parentNode.left !== currentNode) {
      currentNode = parentNode;
      parentNode = parentNode.parent;
    }

    return parentNode;
  }
}

function leftMostChild(node) {
  if (!node) {
    return null;
  }
  while (node.left) {
    node = node.left;
  }
  return node;
}

isBalanced.js

'use strict';

function BinarySearchTree() {
  this.root = null;
}

var Util = {

  getHeight : function (root) {
    if (root === null) { // Base case
      return 0; 
    }
    return Math.max(Util.getHeight(root.left), Util.getHeight(root.right)) + 1;
  },

  isBalanced : function (root) {
    if (root === null) { // Base case
      return true;
    }
    var heightDifference = Math.abs(Util.getHeight(root.left) - Util.getHeight(root.right));
    if (heightDifference > 1) {
      return false;
    } else {
      return Util.isBalanced(root.left) && Util.isBalanced(root.right);
    }
  }

};

// Create a new Balanced Binary Tree as a sample input
// http://js-interview.tutorialhorizon.com/2015/10/12/create-a-binary-search-tree-in-javascript/
var BST = new BinarySearchTree();
BST.insertNode(8);
BST.insertNode(3);
BST.insertNode(10);
BST.insertNode(1);
BST.insertNode(6);
BST.insertNode(14);
BST.insertNode(4);
BST.insertNode(7);
// BST.insertNode(13);

// Find if the given tree is balanced or not
console.log(Util.isBalanced(BST.root)); // true

// Un-comment L#39 to make tree imbalanced
console.log(Util.isBalanced(BST.root)); // false

isBalancedOptimized.js

'use strict';

function BinarySearchTree() {
  this.root = null;
}

var Util = {

  checkHeight : function (root) {
    if (root === null) { // Base case
      return 0;
    }
    var leftHeight = Util.checkHeight(root.left);
    var rightHeight = Util.checkHeight(root.right);
    var heightDifference = leftHeight - rightHeight;
    if (Math.abs(heightDifference) > 1) {
      return -1;
    } else {
      return Math.max(leftHeight, rightHeight) + 1;
    }
  },

  isBalanced : function (root) {
    if (root === null) { // Base case
      return true;
    }
    if (Util.checkHeight(root) === -1) {
      return false;
    } else {
      return Util.isBalanced(root.left) && Util.isBalanced(root.right);
    }
  }

};

// Create a new Balanced Binary Tree as a sample input
// http://js-interview.tutorialhorizon.com/2015/10/12/create-a-binary-search-tree-in-javascript/
var BST = new BinarySearchTree();
BST.insertNode(8);
BST.insertNode(3);
BST.insertNode(10);
BST.insertNode(1);
BST.insertNode(6);
BST.insertNode(14);
BST.insertNode(4);
BST.insertNode(7);
// BST.insertNode(13);

// Find if the given tree is balanced or not
console.log(Util.isBalanced(BST.root)); // true

// Un-comment L#47 to make tree imbalanced

isBST.js

'use strict';

function BinaryTree () {
  this.root = null;
}

var last_logged;

function isBST (root) {

  if (root === null) { // base case
    return true;
  }
  
  // Verify and recurse left
  if (!isBST(root.left)) {
    return false;
  }

  // Verify the current node
  if (last_logged !== null && root.data <= last_logged) {
    return false;
  }

  // Log the current data for debugging and update the last_logged
  console.log('Current Node : ', root.data);
  last_logged = root.data;

  // Verify and recurse left
  if (!isBST(root.right)) {
    return false;
  }

  return true;
}

// Create a Binary Tree as a sample input
var root = {
  data : 8,
  left : null,
  right : null
};
var n1 = {
  data : 10,
  left : null,
  right : null
};

var n2 = {
  data : 6,
  left : null,
  right : null
};

var BT = new BinaryTree();
BT.root = root;

// Create a Binary Search Tree (BST) and Verify  
BT.root.left = n2; 
BT.root.right = n1; 
console.log(isBST(BT.root)); // true

// Create a non-BST and Verify 
BT.root.left = n1; 
console.log(isBST(BT.root)); // false

json-array.js

'use strict';

function createGraph(data, startVal, endVal, intervalRange) {

  // calculate the number of buckets
  var dataPoints = Math.ceil((endVal - startVal) / intervalRange) + 1;

  // create a new array with necessary number of buckets and initialize them with 0
  var graphData = new Array(dataPoints).fill(0);
  var index;

  Object.keys(data).forEach(function(k) {
    index = Math.floor((k - startVal) / intervalRange);
    graphData[index] += data[k];
  });

  console.log(graphData);
}

var d = {
  25: 55,
  26: 45,
  27: 10,
  28: 20,
  30: 1,
  31: 1,
  32: 3,
  33: 10,
  60: 10,
  64: 5,
  65: 5
};

createGraph(d, 20, 65, 5);

post-order-traversal.js

'use strict';

function BinarySearchTree() {
  this.root = null;
}

BinarySearchTree.prototype.postOrderTraversal = function (root) {

  if (root.left) {
    this.postOrderTraversal(root.left);
  } 
  if (root.right) {
    this.postOrderTraversal(root.right);
  }
  console.log(root.data);
  
};

// Create a new Balanced Binary Tree as a sample input
// http://js-interview.tutorialhorizon.com/2015/10/12/create-a-binary-search-tree-in-javascript/
var BST = new BinarySearchTree();
BST.insertNode(10);
BST.insertNode(15);
BST.insertNode(5);
BST.insertNode(2);
BST.insertNode(3);
BST.insertNode(12);
BST.insertNode(17);

BST.postOrderTraversal(BST.root);

pre-order-traversal.js

'use strict';

function BinarySearchTree() {
  this.root = null;
}

BinarySearchTree.prototype.preOrderTraversal = function (root) {
  console.log(root.data);

  if (root.left) {
    this.preOrderTraversal(root.left);
  } 
  if (root.right) {
    this.preOrderTraversal(root.right);
  }
};

// Create a new Balanced Binary Tree as a sample input
// http://js-interview.tutorialhorizon.com/2015/10/12/create-a-binary-search-tree-in-javascript/
var BST = new BinarySearchTree();
BST.insertNode(10);
BST.insertNode(15);
BST.insertNode(5);
BST.insertNode(2);
BST.insertNode(3);
BST.insertNode(12);
BST.insertNode(17);

BST.preOrderTraversal(BST.root);

printNodeAtLevelK.js

const printNodesAtLevelK = (root, k) => {
  
  if (root === NULL) {
    return;
  }
  
  if (k === 0) {
    console.log(`Node at Level k = ${root.data}`);
    return;
  } else {
    printNodesAtLevelK(root.left, k-1);
    printNodesAtLevelK(root.right, k-1);
  }
};

printTreeInLevelOrder.js

var BST = new BinarySearchTree()

BST.insertNode(8)
BST.insertNode(3)
BST.insertNode(10)
BST.insertNode(1)
BST.insertNode(6)
BST.insertNode(14)
BST.insertNode(4)
BST.insertNode(7)
BST.insertNode(13)

function printTreeInLevelOrder (BST) {
  var temp, queue = []
  
  queue.push(BST.root)
  
  while (queue.length) {
    
    // Deque the Queue
    temp = queue.splice(0, 1)[0]
    
    console.log(temp.data)
    
    // Enqueue the Queue
    if (temp.left) queue.push(temp.left)
    if (temp.right) queue.push(temp.right)

  }
}

printTreeInLevelOrder(BST) // 8, 3, 10, 1, 6, 14, 4, 7, 13