Amazon Interview Question
SDE-2sTeam: Hydrabad
Country: India
Interview Type: Written Test
//in js
//here node is the at which you want to take the sum of paths.
Tree.prototype.pathSumRecur = function (node){
if (node == undefined){
return [0, 0];
}else if (node.lNode == undefined && node.rNode == undefined){
return [node.n, 1];
} else {
var lData = this.pathSumRecur(node.lNode);
var rData = this.pathSumRecur(node.rNode);
return [lData[0] + rData[0] + node.n * (lData[1] + rData[1]), lData[1] + rData[1]]
}
}
In Java.
Also, create the required Class/Object named Node.
int recursivelyFindTreePathSums (Node currentNode, int parentSumSoFar) {
if (currentNode.getLeftNode() != null && currentNode.getRightNode() != null)
return recursivelyFindTreePathSums(currentNode.getLeftNode(), parentSumSoFar * 10 + currentNode.getValue()) + recursivelyFindTreePathSums(currentNode.getRightNode(), parentSumSoFar * 10 + currentNode.getValue());
else if (currentNode.getLeftNode() != null)
return recursivelyFindTreePathSums(currentNode.getLeftNode(), parentSumSoFar * 10 + currentNode.getValue());
else if (currentNode.getRightNode() != null)
return recursivelyFindTreePathSums(currentNode.getRightNode(), parentSumSoFar * 10 + currentNode.getValue());
else
return parentSumSoFar * 10 + currentNode.getValue();
}
- Vir Pratap Uttam May 10, 2015