Microsoft student Interview Question
StudentsCountry: India
Interview Type: Written Test
Another possible answer is :-
convert this given BST to a sorted doubly linked list in place (this also has 2 pointers analogous to prev and next ptrs).
Now. from the end of the list, find the kth node. This gives the kth maximum element in the given BST.
may be this is an O(n) algorithm and not O(logn).
K’th Largest Element in BST . Learn how to think for such problem and solve with recursion gohired.in/2015/03/kth-largest-element-in-bst-when.html
K’th Largest Element in BST . Learn how to think for such problem and solve with recursion gohired.in / 2015/03/kth-largest-element-in-bst-when.html
I am fixing my previous wrong implementation here:
struct Node {
Node *left;
Node *right;
int data;
};
Node* find_kth_largest(Node *pNode, int& K)
{
Node *pTmp = NULL;
if (pNode == NULL)
return NULL;
if (pNode->right){
pTmp = find_kth_largest(pNode->right, K);
if (pTmp) {
return pTmp;
}
}
if (0 == K) {
return pNode;
}
else {
K--;
if (pNode->left){
pTmp = find_kth_largest(pNode->left, K);
if (pTmp)
return pTmp;
}
}
return NULL;
}
wont work for edge case when the tree has one node and k = 1. it is supposed to return the same node instead of null.
what you did is find min kth and your code won't return data if i is not k which could be wrong
int inorder(node *root ,int k)
{
static int i=0;
if(node)
{
inorder(root->left,k);
i++;
if(i==k)
return node->data;
inorder(root->right,k);
}
}
I got it it is already given it is the binary search tree and it should be sorted in descending order.
Tree is BST with unique number, So if you perform inorder operation,WE will get element in shorted order(ascending order). So perform reverse Inorder operation means RNL(right ,node ,left) that will give element in descending order and we can directly choose Nth maximum from there. worst case complexity O(n)
void FindKthMax(BTNODE* root, int k)
{
if (root == NULL)
{
return;
}
std::stack<BTNODE*> stkNode;
BTNODE* p = root;
int nVisited = 0;
while (p != NULL || !stkNode.empty())
{
if (p != NULL)
{
stkNode.push(p);
p = p->rchild;
}
else
{
p = stkNode.top();
stkNode.pop();
if (++nVisited == k)
{
printf("We've got it, Kth maximum number is %c", p->chVal);
break;
}
p = p->lchild;
}
}
if (nVisited < k)
{
printf("Sorry, K overflowed.");
}
}
suppose we have K as global variable or class member initialized for Kth biggest member.
you just need to traverse in In-Order ( visit Right before Left for biggest, else visit Left then Right)
void FindKthBiggest(TreeNode *pNode)
{
if(pNode==NULL)
return;
FindKthBiggest(pNode->Right);
K--;
if(K==0)
{
cout <<endl<<K <<"th biggest="<<pNode->Data<<endl;
return;
}
FindKthBiggest(pNode->Left);
}
The technique is rather opposite to in-order. We visit the right subtree, then root, then left subtree. Whenever we visit a node, we decrement a counter (k). This has to be passed by reference.
Here is the code below in C#
public TreeNode FindKthLargestInBST(TreeNode root, int K)
{
int counter = K;
return FindKthLargestInBST(root, ref counter);
}
public TreeNode FindKthLargestInBST(TreeNode root, ref int K)
{
if (root == null)
return null;
TreeNode result;
result = FindKthLargestInBST(root.right, ref K);
if (result != null) return result;
if (K == 1) return root;
K--;
result = FindKthLargestInBST(root.left, ref K);
if (result != null) return result;
return null;
}
//.... finding the Kth maximum element ......here will use...reversed inorder traversal..and while doing that we will get 2nd element.....will take benifit of sorted reversed onorder traversal
..int count =0; // will use this to track no to reach K
public void getKMaximum(Node root, Int k)
{
if(!root && count<=k)
{
getKMaximum(root.right,K);
count++;
if(count== k )
display root.data.
getKMaximum(root.left,K);
}
}
The answers above are flawed in that not all recursive calls return value.
- Andy March 12, 2012Here is my answer to the question. I think that this is the correct one. The time complexity of my approach is O(k).
basicalgos.blogspot.com/2012/03/23-find-kth-node-in-binary-search-tree.html
Comments are welcome!