kK
BAN USER@learner.. Thanks for pointing it !! Here I'm pasting the entire code with initialization condition as I've written a typo in the previous code...
public static void main(String[] args){
// assume we have the root node of bst
if( 2*root.value > sum){
findNodesofSum(root.left, root, sum);
}
else if(2*root.value < sum){
findNodesofSum(root, root.right, sum);
}
else{
// this case occurs when 2*root == value
findNodesofSum(root.left, root.right, sum);
}
}
boolean findNodesofSum( Node refer1, Node refer2, int sum ){
// initially refer1 and refer2 are references to the root of the bst
if(refer1.value + refer2.value > sum){
if(findNodeofSum(refer1.left, refer2, sum))
return true;
if(findNodeofSum(refer1, refer2.left, sum))
return true;
}
if(refer1.value + refer2.value < sum){
if(findNodeofSum(refer1.right, refer2, sum))
return true;
if(findNodeofSum(refer1, refer2.right, sum))
return true;
}
if(refer1.value + refer2.value == sum){
print("The desired value is achieved by the sum of"+ refer1.value + " + " + refer2.value);
return true;
}
return false;
}
Sorry for the typo.. Check if this works !!
- kK February 20, 2012
It should be O(n) right? As this logic touches all the nodes of the bst only once or twice. Correct me if I'm wrong.
- kK February 22, 2012