Return pointer to nth node in level-ordered binary tree

Question

Suppose I have this binary tree in level order:

enter image description here

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.

brainless coder · Accepted Answer · 2014-04-30 03:55:23Z

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.

Remember this code assumes that the tree only has left branch, but it you have both left and right to be traversed recursively then the code will need to be modified.
This worked perfectly. I can't believe I didn't think of that. Thanks.

coderkevin · Accepted Answer · 2014-04-30 03:55:22Z

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

AMADANON Inc. · Accepted Answer · 2014-04-30 04:17:28Z

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?

Collectives™ on Stack Overflow

Return pointer to nth node in level-ordered binary tree

3 Answers 3

2 Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Related