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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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.

Method 1 - Using Algo for Kth Smallest Element

We solved - 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.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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;
}