Can we find the kth largest element using inorder traversal without knowing the height of the binary search tree? Or is there a way where we make a new pattern of traversal like "RIGHT ROOT LEFT"
3 Answers
Can we find the kth largest element using inorder traversal without knowing the height of the binary search tree?
Yes we can.
We can do that using some extra space.
We do not necessarily need to do RIGHT-ROOT-LEFT
to find out kth
largest element (Although doing so would avoid usage of extra space).
There are several approaches.
The most basic one is to have a queue.
Whenever you are traversing inorder-ly, keep inserting the values in the queue.
Needless to say, as it is a binary search tree, the queue will be sorted.
Thus the kth
largest element is at queue.size() - 1 - k
index. (Assuming that 0th
largrst is the maximum element, 1st
largest is 2nd maximum and so on)
This approach would require O(n)
extra space regardless of k
To optimize the space used, we can use the information about k
Note that we only need element at (queue.size() - 1 - k)
th index. Thus
we can have a queue of size (k+1)
. Before inserting an element, we will check if the queue has more than k
element, if it has, we would remove one element from front as we do not require it.
After the traversal is done, the kth
largest element would be at the front of the queue.
Here is the java implementation of both the approaches :
import java.util.LinkedList;
import java.util.Queue;
class Node {
int data;
Node left;
Node right;
static Queue<Integer> efficient = new LinkedList<>();
static Queue<Integer> complete = new LinkedList<>();
Node(int n) {
this.data = n;
this.left = null;
this.right = null;
}
public static void inorder(Node node, int k) {
if (node == null) {
return;
}
inorder(node.left, k);
if (efficient.size() > k) {
efficient.poll();
}
efficient.add(node.data);
complete.add(node.data);
System.out.println(efficient.toString());
inorder(node.right, k);
}
public static void main(String[] args) {
Node root = new Node(7);
root.left = new Node(4);
root.left.left = new Node(1);
root.left.right = new Node(5);
root.left.right.right = new Node(6);
root.right = new Node(9);
int k = 2;
inorder(root, k);
System.out.println("Efficient queue size : " + efficient.size() + " " + efficient.peek());
System.out.println("Full queue size : " + complete.size() + " " + complete.toArray()[complete.size() - 1 - k]);
}
}
Run this and you will know how efficient queue grows.
Please note that here, k
should be less than the number of nodes in the tree. If it is not, then the answer would be the smallest element.
Other approaches uses a heap
for more general solution. In such cases the tree is not required to be a binary search tree.
What about this:
- let x be the node corresponding to the minimum element of the tree (e.g.
x = T.root; while (x->right != NULL) { x = x->right; }
) - Now repeat
x = x.predecessor()
k-1 times (obviously, take care of edge case) - return
x
(you've found thek
-th largest element in the tree)
Implementing predecessor and successor methods on a BST isn't hard, and it's easy when nodes have an additional pointer to parent node.
Are you talking about a simple binary tree or any tree like AVL tree?
If I understand correctly, you don't need to know the height at all... Inorder traversal - RIGHT ROOT LEFT - is supposed to go from the highest value to the lowest.
Each time you enter the function, you may increase a static variable(or send another argument to the function) - until you get to K.
You may also maintain a degree tree, and know directly where to go through that tree.