Find nth Smallest Element In Binary Search Tree

In the continuation of Binary Search Tree articles here comes another exciting one. In this article we will see how we can find the nth smallest element in a Binary Search Tree. Let's take the example of binary search tree given in the figure below (Fig 1.0) and see how to find its 3rd smallest element.

Fig 1.0

Explanation - One thing we know for sure that we will have to traverse through this tree if we want to find any element, if so then what could be better than In-Order Traversal in this case because it gives us the nodes in ascending order. Now once we know how to traverse in ascending order only thing left is to take a counter to check whether we have traversed the n (3 in this example) nodes. Once the counter reach the value n we know its our nth smallest element. We will use the similar approach in the implementation give below, we will traverse the tree using In-Order traversal and take a counter to check the number of nodes we have traversed and as soon as the counter reaches the value 3 we will know this our element (3rd smallest).

Implementation -

package ds.tree;

import ds.tree.BStree.Node;

public class FindNthSmallestBst {
	
	private static int count;

	public static int findNthSmallest(BStree bst, int k) {
		count = 0;
		return findInOrder(bst.getRoot(), k).getData();
	}
	
	private static Node findInOrder(Node root, int k) {
		if(root == null)
			return null;
		
		Node left = findInOrder(root.left, k );
		if(left != null)
			return left;
		count++;
		if(count == k)
			return root;
		
		return findInOrder(root.right, k);
	}
}
  

Custom BST (BStree.java) -

package ds.tree;

public class BStree {

	private Node root;

	public Node getRoot() {
		return root;
	}

	public BStree(int rootData) {
		this.root = new Node(rootData);
	}
	
	public BStree(Node root) {
		this.root = root;
	}

	static class Node {
		int data;
		Node left;
		Node right;

		public Node(int data) {
			this.data = data;
		}
		public int getData() {
			return data;
		}
	}

	public void insert(int data) {
		Node nNode = new Node(data);
		
		Node root = this.root;
		Node nodeB = null;
		while (root != null) {
			nodeB = root;
			if (root.data > data) {
				root = root.left;
			} else {
				root = root.right;
			}
		}
		if(data < nodeB.data)
			nodeB.left = nNode;
		else
			nodeB.right = nNode; 
	}
 }

Main method -

package ds.tree;

public class BtreeMain {
	
	public static void main(String[] args) {
		BStree bst = new BStree(10);
		bst.insert(5);
		bst.insert(3);
		bst.insert(8);
		bst.insert(10);
		bst.insert(6);
        	bst.insert(4);
        	bst.insert(2);
        
        	System.out.println("3rd smallest element is - " + FindNthSmallestBst.findNthSmallest(bst, 3));
	}
}

Output : 3rd smallest element is - 4

Similarly if we want to get the nth largest element we can traverse the tree in decreasing order (Right, Root, Left) and apply the same logic as given above.
We use Morris Traversal also to find the nth smallest element because Morris Traversal is also a way of In-Order traversal which is non recursive.