Amazon Interview Question: 1) how do find out if there i... | Glassdoor

Amazon

## Interview Question

Software Development Engineer In Test 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