Thursday, 19 September 2013

Finding if a number is equal to sum of 2 nodes in tree

Finding if a number is equal to sum of 2 nodes in tree

Here is my code that for this. I am traversing the whole tree and then
doing a find on each node. find() takes O(log n) and so the whole program
takes O(n log n) time.
Is there a better way to implement this program? I am not just talking of
better in terms of time complexity but in general as well. How best to
implement this?
public boolean searchNum(BinTreeNode node, int num) {
//validate the input
if(node == null) {
return false;
}
// terminal case for recursion
int result = num - node.item;
//I have a separate find() which finds if the key is in the tree
if(find(result)) {
return true;
}
return seachNum(node.leftChild, num) || searchNum(node.rightChilde, num);
}
public boolean find(int key) {
BinTreeNode node = findHelper(key, root);
if (node == null) {
return false;
} else {
return true;
}
}
private BinTreeNode findHelper(int key, BinTreeNode node) {
if (node == null) {
return null;
}
if(key == node.item) {
return node;
}
else if(key < node.item) {
return findHelper(key,node.leftChild);
}
else {
return findHelper(key,node.rightChild);
}
}

No comments:

Post a Comment