Yahoo Interview Question
Software Engineer / DevelopersThere is really no point for recursion here. I think that using recursion at these places is actually not a good practice. Though on a similar lines using iteration, this code looks more efficient to me:
Nodeptr nthInInorder(Nodeptr root, int x){
Nodeptr curr = root;
int countedIn = 0, leftchildren = 0, currIn=0;
while(curr!=NULL){
if(curr->left == NULL)
leftchildren = 0;
else
leftchildren = (curr->left)->data + 1;
currIn = countedIn + leftchildren + 1;
if(currIn == x)
return curr;
else if(currIn > x)
curr = curr->left;
else if(currIn < x)
{ countedIn = currIn + 1;
curr = curr->right;
}
}
return NULL;
}
In main() call
- czpete October 11, 2010