## Ebay Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**Phone Interview

I traversed it in reverse as we need largest , else its same a inorder traversal just RNL instead of LNR .

Your algo is O(N).

Small optimization: It would be better to quit the traversal once u find that node.

i would suggest minor change to avoid printing multiple elements...

```
public class KthLargestBST
{
static int count = 0;
public static void kThLast(Tree root, int k)
{
if (root != null)
{
kThLast(root.right, k);
count++;
if (count == k)
{
System.out.println(root.data);
//This will avoid printing rest elements while returning
count++;
return;
}
kThLast(root.left, k);
}
}
}
```

Use inorder traversal and find the (n-k)th element which will be the kth largest element in the tree having n nodes

@bulelaugh: that's only possible for general balanced BSTs if the tree carries some extra information to enable this operation. See "Order Statistic Tree" on Wikipedia.

//Add one more property in the nodes (as no of nodes in subtree rooted at node)

// node.noOfNodes = node.left.noOfNodes+node.right.noOfNodes + 1

//leafNode.noOfNodes = 1

findKthLargest(Node node,int k)

{

if(node != null)

{

if(node.NoOfChild > k )

findKthLargest(node.right, n-k)

else if(node.NoOfChild == k )

return node.data

}

}

```
public TreeNode kthLargestNode(int k) {
return kthLargestNodeT(root, k);
}
private TreeNode kthLargestNodeT(TreeNode node, int k) {
if (node == null) {
return null;
}
int L = sizeOfBSTT(node.left) + 1;
if (L == k) {
return node;
}
if (L > k) {
return kthLargestNodeT(node.left, k);
} else {
return kthLargestNodeT(node.right, k - L);
}
}
public int sizeOfBST() {
return sizeOfBSTT(root);
}
private int sizeOfBSTT(TreeNode node) {
if (node == null) {
return 0;
}
return sizeOfBSTT(node.left) + 1 + sizeOfBSTT(node.right);
}
```

```
public TreeNode<Integer> kthBST(TreeNode<Integer> root, int k) {
if(root == null)
return null;
if(k < 0)
return null;
int left = size(root.left);
if(k == left + 1)
return root;
else if(k < left)
return kthBST(root.left, k);
else
return kthBST(root.right, k - left - 1);
}
private int size(TreeNode<Integer> root) {
if(root == null)
return 0;
return size(root.left) + size(root.right) + 1;
}
```

public class KthLargestBST {

- Arjun December 16, 2012static int count = 0;

public static void kThLast(Tree root, int k) {

if (root != null) {

kThLast(root.right, k);

count++;

if (count == k) {

System.out.println(root.data);

return;

}

kThLast(root.left, k);

}

}

}