Better way to search for a node in binary tree

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.}