Kth Largest in a BST

Basic Solution - Inorder traversal

As we know, the inorder traversal of a given Binary Search Tree always the elements sorted in increasing order.

For Example, Consider the below tree:

        [10]
        /    \
    [5]     [15]
    /   \    /   \
[1]    [7] [11]  [18]

The inorder traversal of this tree will be [1, 5, 7, 10, 11, 15, 18]. This is because Inorder traversal follows left -> root -> right traversal property.

1. Create an array sortedNodeValues that will store the inorder traversal of the given Binary Search Tree.
2. The inorder method will first traverse the left subtree, then add the root value in the sortedNodeValues array and finally will traverse the right subtree.
3. Now since the sortedNodeValues array contains the sorted values, we can simply print sortedNodeValues[sortedNodeValues.length - k] values to get the 3rd largest from the end. This will be our solution.

Complexity Analysis

• Time: O(n) Since we will be visiting the all the nodes atleast once.
• Space: O(n) Since this can be a skewed tree of height n.

Reverse Inorder Approach

Here, we are going to take a different approach. Instead of traversing the array completely and then taking the value from the end of the array, we are going to traverse the array in descending order. As and when we reach the value that we need, (let's say third largest) - we stop and return the value.

1. We declare a class TreeInfo that has lastVisitedNode and numberOfVisitedNodes variables. These are required because we need to compare these against the kth value which is given by the problem.
2. To reverse Inorder traverse an array, we simply traverse it as right -> root -> left. Thisi way, the highest value gets traversed first.
3. While traversing, we check if numberOfVisitedNodes >= k. If this is the case, we simply return the lastVisitedNode because that will be the answer. This will be the base case.
4. Traverse the right subtree by passing tree.right in the reverseInorder() function.
5. If the numberOfVisitedNodes of TreeInfo class is less than k, Increment the count, Mark the last visited as the current node and finally traverse the right subtree.
6. Return lastVisitedNode at the end.