1. Without extra field in Node structure --
Do inorder traversal and count number of node visited. When count is equal to n return the node.
void BSTree::findNthElem(Node* node, int& n, int& retval)
{
if(!node && n)
retval = -1;
else if(n)
{
findNthElem(node->left, n, retval);
if(n)
{
n = n - 1;
if(n == 0)
retval = node->data;
findNthElem(node->right, n, retval);
}
}
}
Do inorder traversal and count number of node visited. When count is equal to n return the node.
void BSTree::findNthElem(Node* node, int& n, int& retval)
{
if(!node && n)
retval = -1;
else if(n)
{
findNthElem(node->left, n, retval);
if(n)
{
n = n - 1;
if(n == 0)
retval = node->data;
findNthElem(node->right, n, retval);
}
}
}
the program runs fine..
ReplyDeletebut the logic is not clear to me..
please share the algo too..
this question was asked in last sem.. i gave a very lengthy approach.. this looks good, but am unable to understand this completely.. please share the ALGO for this one..
Algorithm is very simple.Use Inorder traversal. It always outputs in sorted order.
ReplyDeleteWe are maintaining here a counter 'n' which is decremented when inorder traversal outputs a number. When n is equal to zero. We have our number :)