PROBLEM DESCRIPTION
Given a Binary Search Tree. Your task is to complete the function which will return the Kth largest element without doing any modification in Binary Search Tree.
SOLUTION
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
31
32
33
class Solution
{
int count = 0;
int result = -1;
public int kthLargest(Node root,int K)
{
kthLargestHelper(root, K);
return result;
}
public void kthLargestHelper(Node root, int k){
if(root == null || count >= k)
return;
kthLargestHelper(root.right, k);
count++;
if(count == k){
result = root.data;
return;
}
kthLargestHelper(root.left, k);
}
}
WITHOUT USING GLOBAL VARIABLE
Thanks to Neha Bansal for helping with this 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
31
32
33
34
35
36
37
class Solution
{
public int kthLargest(Node root,int K)
{
return kthLargest(root, K, new Count(0));
}
public int kthLargest(Node root, int K, Count count){
if(root == null)
return -1;
int right = kthLargest(root.right, K, count);
if (right != -1) {
return right;
}
count.c++;
if(count.c == K)
return root.data;
return kthLargest(root.left, K, count);
}
}
class Count{
int c=0;
Count(int c){
this.c = c;
}
}