Find Kth largest in a BST - Given a BST and a number k, find the kth largest element in the BST.
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:
 / \   / \ / \    
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.
sortedNodeValuesthat will store the inorder traversal of the given Binary Search Tree.
inordermethod will first traverse the left subtree, then add the root value in the
sortedNodeValuesarray and finally will traverse the right subtree.
sortedNodeValuesarray 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.
O(n)Since we will be visiting the all the nodes atleast once.
O(n)Since this can be a skewed tree of height
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.
numberOfVisitedNodesvariables. These are required because we need to compare these against the
kthvalue which is given by the problem.
right -> root -> left. Thisi way, the highest value gets traversed first.
numberOfVisitedNodes >= k. If this is the case, we simply return the
lastVisitedNodebecause that will be the answer. This will be the base case.
numberOfVisitedNodesof TreeInfo class is less than
k, Increment the count, Mark the last visited as the current node and finally traverse the right subtree.