Finding nth Largest and Smallest Node in Binary Seach Tree

Concept:

In Binary Search Tree,

• When we do the In-Order traversal, nodes will be visited in ascending order.
  In-Order Traversal
  For each Node,
  • Traverse the left subtree
  • Visit the node
  • Traverse the right subtree

  i.e. for above BST, nodes will be visited in following order,
  1 , 3 , 4 , 5 , 8 , 10 , 11

• When we do the Reverse-In-Order traversal, nodes will be visited in descending order.
  Reverse-In-Order Traversal
  For each Node,
  • Traverse the right subtree
  • Visit the node
  • Traverse the left subtree

  i.e. for above BST, nodes will be visited in following order,
  11 , 10 , 8, 5 , 4 , 3 , 1

In both the above scenarios while visiting each node we just need to update the count of visited nodes. When count equals the n then it means that current node is the required one.
[showads ad=inside_post]
Code:

We have designed a class to return the Nth Largest and Smallest Node in BST using above concept.

class BSTNthNodeFinder
{

	int indexValueCurr;
	node * pResultNode;
	void countNode(node * pRoot)
	{
		indexValueCurr--;
		if(indexValueCurr == 0)
			pResultNode = pRoot;
	}
	void reverseInOrderTraverse(node * pRoot)
	{
		if(pRoot == NULL || pResultNode != NULL)
			return;
		reverseInOrderTraverse(pRoot->pRight);
		countNode(pRoot);
		reverseInOrderTraverse(pRoot->pLeft);
	}
	void inOrderTraverse(node * pRoot)
	{
		if(pRoot == NULL || pResultNode != NULL)
			return;
		inOrderTraverse(pRoot->pLeft);
		countNode(pRoot);
		inOrderTraverse(pRoot->pRight);
	}

public:
	BSTNthNodeFinder()
	{
		indexValueCurr = 0;
		pResultNode = NULL;
	}
	node * findNthLargestNode(node * pRoot, int n)
	{
		indexValueCurr = n;
		pResultNode = NULL;
		reverseInOrderTraverse(pRoot);
		return pResultNode;
	}
	node * findNthSmallestNode(node * pRoot, int n)
	{
		indexValueCurr = n;
		pResultNode = NULL;
		inOrderTraverse(pRoot);
		return pResultNode;
	}
};

Usage Details

node * pRoot = createTree();
BSTNthNodeFinder nthNodeFinder;
node * pTempNthLrgst = nthNodeFinder.findNthLargestNode(pRoot, 1);
node * pTempNthSmlst = nthNodeFinder.findNthSmallestNode(pRoot, 5);

Thanks.