Return pointer to nth node in level-ordered binary tree

Question

Suppose I have this binary tree in level order:

I want to return a pointer to the 5th node. I am having trouble constructing a function to do so.

Here's what I have so far:

    Node* GetNodeAtCount(Node *r, int x)
    {
        if(r != NULL)
        {
            if(r->count == x) {return r;}
            else
            {
                GetNodeAtCount(r->left, x); // my problem is here
                GetNodeAtCount(r->right, x);
            }
        }
    }

My function only correctly returns the right side of the tree. I cannot figure out a way to call the recursive function separately, since I cannot filter by having a "greater than" or "less than" comparison, i.e. to go to the right subtree, left subtree, etc.

Answer 1

You need to call the left tree recursively, may be something like this would work -

Node* GetNodeAtCount(Node *r, int x)
{
    if(r != NULL)
    {
        if(r->count == x) {return r;}

        Node *temp = GetNodeAtCount(r->right, x); //check right tree for match
        if (temp != NULL)
            return temp;
        return GetNodeAtCount(r->left, x); // if right tree does not match further go into left tree
    }
    return NULL //return NULL if it is the end of tree so that the check temp != NULL will work correctly
}

let me know if this helps you.

Answer 2

If your tree is sorted by count, then you can compare and branch from there:

else if (x < r->count && r->left != NULL) { return GetNodeAtCount(r->left, x); }
else if (x > r->count && r->right != NULL) { return GetNodeAtCount(r->right, x); }
else { return NULL; }

Don't forget to check r->left and r->right for NULL values! Note the return calls in those lines as well.

If your tree is not sorted by count, then you'll have to check for the return values.

else
{
    Node *ret;
    ret = (r->left != null ? GetNodeAtCount(r->left, x) : NULL);
    ret = (ret == NULL && r->right != null  ? GetNodeAtCount(r->right, x) : ret);
    return ret;
}

However, if you're using a tree without it being sorted, you should reconsider your data structure and perhaps use something more fitting. Even a vector/array would be faster than searching an unsorted tree. If you're using a tree because you're sorting for some other field, consider a B+ tree.

http://en.wikipedia.org/wiki/B%2B_tree

Answer 3

I am not familiar with C++, so this will be pseudocode:

If the current node does not exists:
    return failure

If (the node is the one you are after):
   return the current node

result=recurse(left node)

if result != failure:
   return result

return recurse(right node) // which may be failure

Edited, to add check for "current node does not exist" at the start; this simplifies the rest of the code. I think in C++ you compare to null object?