Ebay Interview Question
Software Engineer / DevelopersCountry: 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);
}
}
}