Get node number XX in BST

[hmortensen]

Hi All,

I'm trying to make a routine that returns node number XX from a BST.

The nodes are as follows:

struct Node
{
	signed int	type;
	Node*		child1;
	Node*		child2;
};

I can easily count the number of nodes by

long Pheno::CountNodes(Node* n)
{
	if(n==NULL)
		return 0;
	return(Pheno::CountNodes(n->child1)+1+Pheno::CountNodes(n->child2));
}

But I can't figure out how to count myself to node # XX and return it.?? Doesn't matter if it is depth or breath first.

Hope someone out there can help.

Thanks,

- hmortensen

[hmortensen]

I solved it.. Not pretty, so if anyone out there have a more clean way of doing it, please reply

Node* Pheno::GetNode(long& i,long& c,Node* sn)
{
	if(sn==NULL)
		return NULL;
	if(i==c)
	{
		return sn;
	}
	c++;
	Pheno::GetNode(i,c,sn->child1);
	if(i==c)
	{
		return sn;
	}
	Pheno::GetNode(i,c,sn->child2);
	return NULL;
}

Made the counter common for all the calls. That worked, and the extra check, between child 1 and 2.

[Tom Gunn]

Not pretty, so if anyone out there have a more clean way of doing it, please reply

With a recursive algorithm that is about the best way to do it. A cleaner and more powerful way is by writing an iterator for your BST. Traversal with iterators can be stopped and started without forcefully breaking out of a recursive call chain, so the algorithm is more elegant:

Node* Pheno::GetNode(long const i)
{
    if (i < 0 || i > size()) return NULL;

    Iterator current(begin());

    while (current != end() && --i >= 0) ++current;

    return current->Node;
}

But that means you have to write a lot of framework to support iterators, and it is more complex than recursive traversal. If you are interested in learning more, a good place that describes one way is here.

[hmortensen]

With a recursive algorithm that is about the best way to do it.

hmm. Ok, had my hopes up. :-/

A cleaner and more powerful way is by writing an iterator for your BST.

For my current project, it would be overkill. But maybe it would help me, in one of my other projects. So Ill take a deeper look into iterator for BST.

Thanks for your feedback.