Created
April 3, 2017 18:13
-
-
Save iagocaldeira/1a0d8e8301e26ffe92bf0faf05112e27 to your computer and use it in GitHub Desktop.
getSumInTree.js
This file contains 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
var _ = require('lodash'); | |
/** | |
* Instructions: | |
* | |
* Write a solution in Node.JS that: | |
* | |
* Given an representation of a binary tree deserialized as string and a number, create a binary tree | |
* and return every path in the tree with sum of the nodes that is equals the given number. | |
* A path can start from any node and end at any node, i.e. they need not be root node and leaf node. | |
* | |
* | |
* Example: | |
* Input: | |
* tree = "1 5 # # 2 3 2 # # 7 # # 1 5 # # 1 # #" | |
* number = 5 | |
* | |
* | |
* Respective binary tree for the given input: | |
* 1 | |
* / \ | |
* 5 2 | |
* / \ | |
* 3 1 | |
* / \ / \ | |
* 2 7 5 1 | |
* | |
* Output: [ 0: [5], 1: [2, 3], 2: [3, 2], 3: [5], 4: [1, 2, 1, 1] ] | |
* | |
* | |
* Rules: | |
* 1. Do not create global scope. We have a test runner that will iterate on your function and run many fixtures through it. | |
* 2. The left sub-tree has priority over the right sub-tree. | |
* | |
* Common Questions: | |
* 1. What's a binary tree? A binary tree is made of nodes, where each node contains a "left" reference, a "right" reference, and a data element. | |
* 2. What does the # mean? It means null nodes. | |
* 3. Can I use outside packages to solve (e.g. NPM, Bower)? Yes. You can use any packages you want to solve the solution. | |
* 4. Can I use google or outside resources (e.g. StackOverflow, GitHub)? Yes. Act as you would in your day job. | |
* 5. How should I send my solution? You must send the solution by email to diego@tenfold.com cc'ing kessiler@tenfold.com. | |
* | |
* | |
* | |
* @param tree is a string with the representation of tree | |
* @param number is an random number - Note: it can be a floating point | |
* @return an array with the nodes values in it or an empty array | |
*/ | |
exports.getSumInTree = function( tree, number) { | |
var Node = function(val){ | |
this.value = val; | |
this.left = null; | |
this.right = null; | |
} | |
function BinaryTree(){ | |
this.root = null; | |
} | |
BinaryTree.prototype.push = function(val){ | |
var root = this.root; | |
if(!root){ | |
root = new Node(val); | |
return; | |
} | |
var currentNode = root; | |
var lastNode = root; | |
while(currentNode){ | |
if(!currentNode.left){ | |
currentNode.left = new Node(val); | |
break; | |
}else if(currentNode.left.val=="#"){ | |
if(currentNode.right.val=="#"){ | |
currentNode = lastNode.right; | |
}else{ | |
currentNode = currentNode.right; | |
} | |
}else if(currentNode.left){ | |
lastNode = currentNode; | |
currentNode = currentNode.left; | |
} | |
else if(!currentNode.right){ | |
currentNode.right = new Node(val); | |
break; | |
}else if(currentNode.right.val=="#"){ | |
currentNode = lastNode.right; | |
}else if(currentNode.right){ | |
currentNode = currentNode.right; | |
} | |
} | |
} | |
var pushArray = function(arr,binT){ | |
arr = arr.split(" "); | |
for (var i = 0; i < arr.length; i++) { | |
binT.push( arr[i]=="#" ? "#" : parseInt(arr[i]) ); | |
} | |
return binT; | |
} | |
var binT = new BinaryTree(); | |
bitT = pushArray(tree,binT); | |
var findSum = function (number,binT) { | |
var output = []; | |
var totalSum = 0; | |
var currentNode = binT.root; | |
var lastNode = binT.root; | |
var nodeStack = []; | |
while(currentNode){ | |
if((totalSum + currentNode.val) < 5){ | |
nodeStack.push([currentNote, currentNode.val]); | |
totalSum += currentNode.val; | |
} else if((totalSum + currentNode.val) == 5){ | |
nodeStack.push([currentNote, currentNode.val]); | |
output.push(nodeStack); | |
output = []; | |
totalSum = 0; | |
} else if((totalSum + currentNode.val) > 5){ | |
totalSum -= nodeStack.pop().val; | |
if(nodeStack[nodeStack.length - 1]){ | |
currentNode = nodeStack[nodeStack.length - 1]; | |
return output; | |
} | |
if(nodeStack[nodeStack.length - 2]){ | |
lastNode = nodeStack[nodeStack.length - 2]; | |
}else{ | |
lastNode = binT.root; | |
} | |
} | |
if(currentNode.left.val == "#"){ | |
if(currentNode.right.val=="#"){ | |
if(nodeStack[nodeStack.length - 1]){ | |
currentNode = nodeStack[nodeStack.length - 1]; | |
return output; | |
} | |
if(nodeStack[nodeStack.length - 2]){ | |
currentNode = nodeStack[nodeStack.length - 2]; | |
}else{ | |
currentNode = lastNode; | |
} | |
}else{ | |
lastNode = currentNode; | |
currentNode = currentNode.right; | |
} | |
}else if(currentNode.right.val == "#"){ | |
if(nodeStack[nodeStack.length - 1]){ | |
currentNode = nodeStack[nodeStack.length - 1]; | |
return output; | |
} | |
if(nodeStack[nodeStack.length - 2]){ | |
currentNode = nodeStack[nodeStack.length - 2]; | |
}else{ | |
currentNode = lastNode; | |
} | |
} | |
} | |
} | |
return findSum(number,binT); | |
} | |
var tree = "1 5 # # 2 3 2 # # 7 # # 1 5 # # 1 # #"; | |
var number = 5; | |
this.getSumInTree(tree,number); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment