BST
Binary Search 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.


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.

Join a list of 2000+ Programmers for latest Tips & Tutorials