Skip to content

Instantly share code, notes, and snippets.

@marcogbarcellos
Last active February 14, 2021 19:55
Show Gist options
  • Save marcogbarcellos/c2df66422f6b3f296243fc1a0d7100d6 to your computer and use it in GitHub Desktop.
Save marcogbarcellos/c2df66422f6b3f296243fc1a0d7100d6 to your computer and use it in GitHub Desktop.
Creating, manipulating and calculating distance between nodes inside a Binary Search Tree
function Node(value){
this.value = value;
this.left = null;
this.right = null;
}
function BinarySearchTree() {
this.root = null;
}
BinarySearchTree.prototype.push = function (val) {
if(this.root === null) {
this.root = new Node(val);
}
else {
var currentNode = this.root;
while (currentNode != null) {
if (val < currentNode.value) {
if (currentNode.left == null) {
currentNode.left = new Node(val);
break;
} else {
currentNode = currentNode.left;
}
} else {
if (currentNode.right == null) {
currentNode.right = new Node(val);
break;
} else {
currentNode = currentNode.right;
}
}
}
}
}
function distanceFromNode (node, value) {
if(node == null) {
//if return null it's going to sum with the prior results(in javascript the operation (1+null=1) )
return undefined;
}
if(node.value == value) {
return 0;
} else {
if(value < node.value) {
return 1+distanceFromNode(node.left,value);
} else if(value > node.value){
return 1+distanceFromNode(node.right,value);
}
}
}
function findLowestCommonAncestor (node, value1, value2) {
if(node == null) {
return null;
}
if(node.value > value1 && node.value > value2) {
return findLowestCommonAncestor(node.left, value1, value2);
}
if(node.value < value1 && node.value < value2) {
return findLowestCommonAncestor(node.right, value1, value2);
}
return node;
}
// returns the Distance between two nodes given the root of the Binary Tree and 2 random values
function distanceBetweenTwoNodes(root, value1, value2) {
var common = findLowestCommonAncestor(root, value1, value2);
if(common == null || common == undefined) {
return -1;
}
if( distanceFromNode(common,value1) == -1 ) {
return -1;
}
if( distanceFromNode(common,value2) == -1 ) {
return -1;
}
return distanceFromNode(common,value1) + distanceFromNode(common,value2);
}
function distanceBetweenTwoNodes(root, value1, value2) {
var common = findLowestCommonAncestor(root, value1, value2);
if(common == null || common == undefined) {
return -1;
}
if( distanceFromNode(common,value1) == -1 ) {
return -1;
}
if( distanceFromNode(common,value2) == -1 ) {
return -1;
}
return distanceFromNode(common,value1) + distanceFromNode(common,value2);
}
function sumFromUpperNodeToLowerNode (upperNode, lowerNode) {
if (upperNode == null || lowerNode == null ) {
//if return null it's going to sum with the prior results(in javascript the operation (1+null=1) )
return undefined;
}
if(upperNode === lowerNode) {
return lowerNode.value;
} else {
if(upperNode.value < lowerNode.value) {
return upperNode.value + sumFromUpperNodeToLowerNode(upperNode.right,lowerNode);
} else if(upperNode.value > lowerNode.value){
return upperNode.value + sumFromUpperNodeToLowerNode(upperNode.left,lowerNode);
}
}
}
function findSumBetweenTwoNodes (root, node1, node2) {
var common = findLowestCommonAncestor(root, node1.value, node2.value);
if(common == null || common == undefined) {
return undefined;
}
return sumFromUpperNodeToLowerNode(common,node1) +
sumFromUpperNodeToLowerNode(common,node2) -
common.value;
}
function findNodeInTree(root, value) {
if (root == null) {
return null;
}
if(root.value === value) {
return root;
} else {
if(value < root.value) {
return findNodeInTree(root.left, value);
} else {
return findNodeInTree(root.right, value);
}
}
}
/*
Test your code through here(main func)
*/
function testCode() {
var test = [9,5,7,6,8,4,11,20,3,17,19,1,45,2];
// 9 -> 11 -> 20 -> 45;
// 9 -> 11 -> 20 -> 17 -> 19
// 9 -> 5 -> 4 -> 3 -> 1 -> 2
// 9 -> 5 -> 7 -> 6
// 9 -> 5 -> 7 -> 8
// 9
// 5 11
// 4 7 20
// 3 6 8 17 45
// 1 19
// 2
var binaryTree = new BinarySearchTree();
var root = new Node(test[0]);
binaryTree.root = root;
for(var i = 1; i < test.length; i++) {
binaryTree.push(test[i]);
}
/* To test DISTANCE between nodes */
// console.log(distanceBetweenTwoNodes(binaryTree.root,3,8)); //Should return 4
// console.log(distanceBetweenTwoNodes(binaryTree.root,9,6)); //Should return 3
// console.log(distanceBetweenTwoNodes(binaryTree.root,9,20)); //Should return 2
// console.log(distanceBetweenTwoNodes(binaryTree.root,-9,-6)); //Should return -1
// console.log(distanceBetweenTwoNodes(binaryTree.root,9,-19)); //Should return -1
// console.log(distanceBetweenTwoNodes(binaryTree.root,3,20)); //Should return 5
// console.log(distanceBetweenTwoNodes(binaryTree.root,2,19)); //Should return 9
/* To test SUM between nodes */
var node1 = findNodeInTree(binaryTree.root, 2);
var node2 = findNodeInTree(binaryTree.root, 19);
console.log('node1:',node1);
console.log('node2:',node2);
var sum = findSumBetweenTwoNodes (binaryTree.root, node1, node2);
console.log('result SUM: ',sum); //should return 91
}
//running the main func to test the code...
testCode();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment