Better way to search for a node in binary tree

This is the code I have written for searching a node in a tree as a part of my assignment:

typedef struct NODE
{
    int key; 
    struct NODE *left, *right; 
} Node;

Node *search(Node *head, int key)
{
    if (!head)
        return 0; 
    if (head->key == key)
        return head; 
    
    return or(search(head->left, key), search(head->right, key)); 
}

Node *or(void *ptr1, void *ptr2)
{
    Node *temp = (Node *)((long)ptr1 | (long)ptr2);
    return temp;
}

I wrote a recursive function because it's the 1st thing that comes to mind when you want to scan a tree. This was supposed to be simple, but it quickly became a dance with pointers (had to do bitwise OR on the Node* pointers).

The function analyzes the left and right sub-trees of a node, returning NULL if node is not found, or the Node address if the key gets matched. In the end, we do a bitwise OR on the two pointers returned which enables us to return the non-zero node address if the key gets matched.

Although this isn't too much code (and it works), I think it is more complicated than necessary. Can anyone recommend a simpler technique? (Recursive preferred)

edit:

Node *left = search(head->left,key) ;
if(left)
return left ; 
else 
return search(head->right,key) ;

This was simply what I could have done without involving myself with bitwise operations on pointers.

Your original approach only works if you can make these assumptions:

• type long is wide enough for the conversion from Node* to long and back to yield the original pointer. This is true on 32-bit systems and 64-bit Unix systems, but not on 64-bit Windows where long is only 32-bit wide and pointers require 64 bits.
• there is at most one Node* with the key value in the tree. Otherwise or-ing the bits of the matching pointers will produce a meaningless result that will invoke undefined behavior.
• performance is not needed as this implementation walks the whole tree for every search with a linear complexity instead of the expected Log(N) complexity.

I wrote original because I have never seen anyone else do it this way! Sadly, it is not a good approach because it is inefficient, non portable and risky, but creativity is a good skill to hone in programming.

Assuming your binary tree is actually constructed as a binary search tree, the classic approach for a look up is to compare the key with the node value and recurse only on the left or right branch as needed:

typedef struct NODE {
    int key; 
    struct NODE *left, *right; 
} Node;

Node *search(Node *head, int key) {
    if (!head)
        return NULL; 
    if (key == head->key)
        return head; 
    if (key < head->key)
        return search(head->left, key);
    else
        return search(head->right, key);
}

This can be simplified a bit with a single terminal recursion:

Node *search(Node *head, int key) {
    if (!head || key == head->key)
        return head;
    else 
        return search(key < head->key ? head->left : head->right, key);
}

Note that an iterative version might perform better:

Node *search(Node *head, int key) {
    while (head && key != head->key) {
        head = key < head->key ? head->left : head->right;
    }
    return head; 
}

Finally, here is a cryptic alternative with fewer branches^(*):

Node *search(Node *head, int key) {
    while (head && key != head->key) {
        head = (key > head->key)[&head->left];
    }
    return head; 
}

If the tree is not sorted (just an ordinary binary tree), you may have to explore the whole tree this way:

Node *search(Node *head, int key) {
    if (!head || key == head->key)
        return head; 
    Node *n = search(head->left, key);
    return n ? n : search(head->right, key);
}

^{(*) Please do not use this kind of code in production, this is just a cryptic example for educational purpose. Here is an explanation: in C a[b] is the same as *(a+b) which is commutative so you can swap the pointer and the index as well and write b[a] with the same effect. (key > head->key) has the value 0 or 1 depending on the comparison, &head->left is the address of the left structure member, adding 1 to this address gives the address of the right member (a tad abusive but should work). So this expression selects the left or right member based on the comparison without an actual branch on modern processors.}