Amazon.com

  www.amazon.com
  www.amazon.com

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?
Answer

Interview Answer

2 Answers

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

Add Answers or Comments

To comment on this, Sign In or Sign Up.