Solution #1: Here is the code,
int getLevel(struct node* root, int n, int level)
{
if(root == NULL)
return 0;
if(root->data == n)
return level;
return getLevel(root->left, n, level+1) | getLevel(root->right, n, level+1);
}
5 comments:
This method can be written without the third parameter...the input provided shud be root and the element whose level is to be determined...right?
@Anonymous: I don't see an "elegant" way to write this function without passing a third parameter. Please feel free to post your solution as a comment and I will include it in the post. Thanks.
int getLevel(struct node* root, struct node* target) {
if( root == NULL ) {
return 0;
}
if( root->data == target-> data ) {
return 0;
}
return 1+getLevel(root->left, target) | 1+getLevel(root->right, target);
}
Both the original solution, and mine, are O( 2^N ) with respect to the number of elements in the tree because of the recursive call. A faster solution would be to use a FIFO Queue. That would result in an O( N ) run-time.
-- Horia Margarit
Right. Basically you are referring to BFS.
This code will deliver the depth of the longest brunch, even if it doesn't include the target node. It won't work correctly! You need an other test before the last line in your code:
...
if( root->left != NULL) {
if( root->left->data == target-> data )
return 1+getLevel(root->left, target)
}
if( root->right != NULL) {
if( root->right->data == target-> data )
return 1+getLevel(root->right, target)
}
return 1+getLevel(root->left, target) | 1+getLevel(root->right, target);
}
And that's the depth, you calculated, not the level.
Best Regards
Konstantin
Post a Comment