implementing FindKth on Binary Trees!

[dumbgeek]

Hello again!

I have the recursive version of the findKth operation, i know that it doesn't have to be recursive but i don't know how to implement it iteratively. Please could you help me with this.

This should be the recursive operation..
//internal method to find Kth item in a subtree
// k is the desired rank
// t is the node that roots the tree
template <class Comparable>
BinaryNode<Comparable> * BinarySearchTreeWithRank<Comparable>::
findKth int k, Node * t) const
{
if (t == NULL )
return NULL;

int leftsize = treeSize(t -> left); \\find sizze of left subtree

if ( k <= leftSize )
return findKth( k, t ->left);
else if(k ==leftSize + 1)
return t;
else
return findKth( k - leftSize - 1, t->right );
}

Please can you tell me how the iterative version will be done

 

[PerFnurt]

Here's a tree implementation:

http://www.codeguru.com/algorithms/RedBlackTree.html

Check its iterator classes to see how to traverse without recursion.


/Per
[sub]
if (typos) cout << &quot;My fingers are faster than my brain. Sorry for the typos.&quot;;
[/sub]