Last active
February 14, 2021 19:55
-
-
Save marcogbarcellos/c2df66422f6b3f296243fc1a0d7100d6 to your computer and use it in GitHub Desktop.
Creating, manipulating and calculating distance between nodes inside a Binary Search Tree
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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