# 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.
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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Scroll to Top