Amazon.com

www.amazon.com
Engaged Employer

Interview

# 1) how do find out if there is a path from root to leaf

whose summation= given number?

0

Here is my solution, please do let me know if it works. class Node{ public int value; public Node left; public Node right; } boolean function pathExists(Node node, int givenNumber){ //first case, if the node is null, conclude false if( node == null ){ return false; } //if reach leave if( node.left == null && node.right == null){ //decision bases on the remaining and the leaf's value return (node.value == givenNumber ); } //keep searching the remaining in node's children return pathExists(node.left, givenNumber - node.value) || pathExists(node.right, givenNumber - node.value); }

Duy on Jan 2, 2012
0

@Duy: we should not check for leaf node since the path may be before we reach leaf as well. so , with a simple change, this should work: if( node == null ){ return false; } //if reach leave else if (node.value == givenNumber ) { return true; } //keep searching the remaining in node's children else return pathExists(node.left, givenNumber - node.value) || pathExists(node.right, givenNumber - node.value); }

Micks on Oct 20, 2012