Kth largest element in Binary Search Tree

Problem

Given a Binary Search Tree (BST) and a positive integer k, find the k’th largest element in the Binary Search Tree.

Examples

Example 1:

Input:
  2
 / \
1   3

and k = 2

Return : 2

As 2 is the second smallest element in the tree.

Solution

This problem is similar to [Kth Smallest Element in a BST](kth-smallest-element-in-a-bst).

Method 1 - Using Algo for Kth Smallest Element

We solved - [Kth Smallest Element in a BST](kth-smallest-element-in-a-bst). We can calculate total nodes n, and then kth largest elemnt will be (n-k)' th smallest element in BST. The problem with this approach is that it requires two traversals of the array.

Method 2 - Use Recursive Reverse Inorder Traversal

By reverse inorder traversal, we mean solving the right child, then node and then left child. We can use recursive solution similar to [Kth Smallest Element in a BST](kth-smallest-element-in-a-bst).

Code

Java

public static int kthLargest(TreeNode root, int k) {
	// count tracks visted node
	AtomicInteger counter = new AtomicInteger(0);
	TreeNode kthNode = helper(root, k, counter);
	return  kthNode == null? -1: kthNode.val;
}

public TreeNode helper(TreeNode root, int k, AtomicInteger counter) {
	// base case
	if (root == null) {
		return null;
	}

	// search in the right subtree
	TreeNode right = kthLargest(root.right, i, k);

	// if k'th largest is found in the left subtree, return it
	if (right != null) {
		return right;
	}

	// if the current node is k'th largest, return its value
	if (i.incrementAndGet() == k) {
		return root;
	}

	// otherwise, search in the left subtree
	return kthLargest(root.left, i, k);
}

Method 2 - Iterative Reverse Order 🏆

Code

Java

public int getNthIterative(TreeNode root, int k) {
	if (root == null) {
		return -1;
	}
	Stack<TreeNode> stack = new Stack<>();
	TreeNode curr = root;

	while (!stack.isEmpty() || curr != null) {
		if (curr != null) {
			stack.push(curr);
			curr = curr.right;
		} else {
			TreeNode node = stack.pop();
			k--;
			if (k == 0) {
				return node.val;
			}
			curr = node.left;
		}
	}
	return -1;
}