## Microsoft student Interview Question for Students

• 0

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
1
of 1 vote

The answers above are flawed in that not all recursive calls return value.

Here 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

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

``gohired.in/2015/03/kth-largest-element-in-bst-when.html``

Comment hidden because of low score. Click to expand.
1
of 3 vote

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;``````

}

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Just please notice that the find utility uses a 0-based logic. So, if the K=1, then this will actually request the second largest item. For the rest of the logic, you can use the code and have it run with any data you find appropriate.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can do using inorder traversal.

Comment hidden because of low score. Click to expand.
0

what you did is find min kth and your code won't return data if i is not k which could be wrong

Comment hidden because of low score. Click to expand.
0

For finding the Kth maximum number, use reverse inorder traversal.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}

Comment hidden because of low score. Click to expand.
0

Before this need to check whether the tree is already sorted or not.

Comment hidden because of low score. Click to expand.
0

I got it it is already given it is the binary search tree and it should be sorted in descending order.

Comment hidden because of low score. Click to expand.
0

I think this returns the kth minimum element. Return (n-k)th element. OR do a reverse inorder traversal.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int FindElement(Node n , int k, int counter){
if(n==null) return 0;
FindElement(n.right,counter);
counter++;
If(k==counter)
return n.data;
FindElement(n.left,counter);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Perform an inorder traversal (if find Kth minimum number) or reverse inorder traversal (if find Kth maximum number), we shall need to maintain the stack ourselves.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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.");
}
}``````

Comment hidden because of low score. Click to expand.
0

I doubt the code may need deal with the case when the tree is extremely unbalanced, for example having no right branch at all

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

struct tree* kthMax(struct tree *root, int *k)
{
struct tree *ptr;

if(root == NULL)
return NULL;
ptr = kthMax(root->right, k);
if(ptr)
return ptr;

*k = *k - 1;
if(*k == 0)
return root;
return kthMax(root->left, k);

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//Finding the kth Maximum in a BST
int found=0,node* nd;
node* k_th_max(node *root,int k)
{

static int count=0;

if(!root)
return (node *)0;

if(root && !found)
{
nd=k_th_max(root->right,k);

if((++count)==k)
{
found=1;
return root;
}

nd=k_th_max(root->left,k);

}
return nd;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Flawless Code... Enjoy!!!

``````node* KthMax(node* root, int k, int &count)
{
if(!root)
return NULL;
node* result = KthMax(root->right,k,count);
if(result)
return result;
else if ( ++count == k )
return root;
else
return KthMax(root->left,k,count);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

//.... 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);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

learn how to think with recuirsion and why to use post order or inorder
K’th Largest Element in BST gohired.in/2015/03/kth-largest-element-in-bst-when.html

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. inorder traversal
2. instead of displaying element just push the element in a stack of size K.
3. once the stack is full, return stack.pop();

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.