как искать узел в двоичном дереве?

Question

node * search(node *root,int k) { 
    if(root == NULL) 
     return NULL; 
    if(root->data == k) 
     return root; 
    else { 
     search(root->left,k); 
     search(root->right,k); 
    } 
    return NULL; 
} 

Я не знаю, почему эта функция не работает? Пожалуйста помоги.

Answer 1

Вы не возвращаете результат рекурсивных вызовов, если узел найден.

node * search(node *root,int k) { 
    if(root == NULL) { 
     return NULL; 
    } else if (root->data == k) { 
     return root; 
    } else { 
     node* x = search(root->left,k); 
     if (x) 
     return x;   //if we find in left subtree, return result 
     return search(root->right,k); 
    } 
}