Finding nth Largest and Smallest Node in Binary Seach Tree

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.
[showads ad=inside_post]
Code:

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

Advertisements

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.

Do you want to Learn Modern C++ from best?

We have curated a list of Best C++ Courses, that will teach you the cutting edge Modern C++ from the absolute beginning to advanced level. It will also introduce to you the word of Smart Pointers, Move semantics, Rvalue, Lambda function, auto, Variadic template, range based for loops, Multi-threading and many other latest features of C++ i.e. from C++11 to C++20.

Check Detailed Reviews of Best Modern C++ Courses

Remember, C++ requires a lot of patience, persistence, and practice. So, start learning today.

Leave a Comment

Your email address will not be published.

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

Scroll to Top