Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
yeah as pawan also mentioned if the tree is unbalanced then u cant even reach the node in time < height and height>=log(n). so if u have to find smallest element n=1 in a BST with 1000 nodes on left you cant even reach it in log(n).
@barcode in case of complete BST it can be done in log(n) time
If you notice the reason we go to each node is because we dont know in which subtree, left or right will nth fall. This wasteful traversal causing O(n)
Well if you modify the data structure and save number of left and right child and assume that it is kind of balanced tree in average case then you can do something near to O(logn).
I think the interviewer was looking if you could come up with this idea.
so, for example BST has 8 nodes and it is unbalanced(node "1" in the root, root.right = 2, root.right.right=3, etc..).
the algorithm should find the kth smallest element(i.e. 6th smallest element which is 6) for logN steps(for 3 steps). Mission seems to be impossible..if the nodes are repeated then it become even more difficult..Does the solution even exist?
Yes. log n seems to be impossible....
Simple logic is - you have to visit each node at least once to check for its value.
I don't get it. Why do we have to visit each node? Why not just go to the min node (left most node) by recursively going to left node until there are no more left nodes. And then once there are no more left most nodes, start storing the nodes in a stack and continue traversing tree in in-order style. Once the size of stack is equal to n, then the top most element of stack will be the result.
Viable solution , I gurantee, is augmenting the BST in such a way that each node stores the nodes in it's left subtree and right subtree. Then it is possilbe for lgn time for subsequent order statistics related query .
A good approach i must say in cases where you are allowed to store data on the node but in this case here the interviewer has already "given you a BST", hence augmentation is not possible.
public void traverseToNThSmallest(Node root) {
if (root.left != null) {
traverseToNThSmallest(root.left);
}
counter++;
if(counter ==nthElement)
{
System.out.println(nthElement+"th element: "+ root.val);
return;
}
if (root.right != null) {
traverseToNThSmallest(root.right);
}
}
public static int findKthElementinBSTInTimeOfLogN(treeNode root,int k){
int[] arr = BSTintoArray(root);
if(k>arr.length) return -1;
return arr[k-1];
}
public static int[] BSTintoArray(treeNode root){
if(root==null) return null;
int[] left = BSTintoArray(root.left);
int[] right = BSTintoArray(root.right);
int l_length = 0;
int r_length = 0;
if(left!=null) l_length = left.length;
if(right!=null)r_length = right.length;
int[] left_new = new int[l_length+1+r_length];
left_new[l_length]=root.data;
if(left!=null){
System.arraycopy(left, 0, left_new, 0, l_length);
}
if(right!=null){
System.arraycopy(right, 0, left_new, l_length+1, r_length);
}
return left_new;
}
find number of elements in left and right subtree. If n lies in left subtree then recursively search for (n - noOfElementsInRightSubtree). Same for right side if n lies in right subtree. The base case would be:
if(n == noOfElementsInLeftSubtree + 1)
return root;
correct it, if i am wrong,
if the BST contains 7 nodes,
number of recursive calls called will be 7 , and the call returns value only after calling the leaf nodes
Node temp;
public Node getNthMin(int target){
if(target==1) return getMin();
else{
int counter=1;
temp=getMin();
while(true){
temp=temp.parent;
counter++;
if(counter==target) return temp;
if(temp.right!=null) {counter++;}
if(counter==target) return temp.right;
}
}
}
public Node getMin(){
temp=root;
while(true){
if(temp.left==null) return temp;
else temp=temp.left;
}
}
Node temp;
public Node getNthMin(int target){
if(target==1) return getMin();
else{
int counter=1;
temp=getMin();
while(true){
temp=temp.parent;
counter++;
if(counter==target) return temp;
if(temp.right!=null) {counter++;}
if(counter==target) return temp.right;
}
}
}
public Node getMin(){
temp=root;
while(true){
if(temp.left==null) return temp;
else temp=temp.left;
}
}
nth smallest would be the nth InOrder successor ryt ?
node* nthsmallest(node * root, int n)
{
node* t = leftmost (root); //Gives the leftmost node in bst
for(int i=0;i<n-1;i++)
{
node*p;
if(t->parent==0 || t->right!=0)
p=leftmost(t->right)
else //go up till we are on left side
{
while((p=t->parent)!=0)
{
if(t=p->left)
break;
t=p;
}
}
//Now p is the inorder successor
t=p;
}
return t;
}
In worst case you can't (say tree that looks like linked list) but on average you can probably do this.
start searching for the smallest with pointer1. After n steps start searching for the smallest in parallel with both pointer1 and new pointer 2. Once pointer1 reached the smallest pointer2 points to the nth smallest.
Actually if traveling BST in-order, we will get the number by ascend, but most of us just do not realize this feature.
So this question will be changed into getting the kth element of BST in-order traverse.
void findK(Node* p, int& k) {
if(!p || k < 0) return;
findK(p->left, k);
--k;
if(k == 0) {
print p->data;
return;
}
findK(p->right, k);
}
int BinaryTree::nthSmallestItem(int nth){
Stack<NodePtr> parent, rightChild;
NodePtr ptr = root;
int counter = nth;
parent.push(ptr);
while(!parent.empty() && counter > 0){
while(ptr != 0){
parent.push(ptr);
if(ptr->right != 0)
rightChild.push(ptr->right);
ptr = ptr->left;
}
ptr = parent.topElement();
parent.pop();
counter--;
if(counter == 0) break;
if(ptr->right != 0){
ptr = rightChild.topElement();
rightChild.pop();
} else{
// important to make ptr null else above while loop will probe same node and code goes into infinite loop
ptr = 0;
}
}
return ptr->data;
}
this would do the preorder of the tree which would give the nth smallest element in O(log n)complexity:
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
using namespace std;
struct node
{
int data;
struct node *right;
struct node *left;
}*root=NULL;
struct node *bst_ins(struct node *root,int n)
{
struct node *temp=root,*temp1;
if(!root)
{
root=new node;
root->data=n;
root->right=NULL;
root->left=NULL;
}
else
{
temp=root;
while(temp)
{
temp1=temp;
if(n>temp->data)
temp=temp->right;
else
temp=temp->left;
}
temp=new node;
temp->data=n;
temp->right=NULL;
temp->left=NULL;
if(n>temp1->data)
temp1->right=temp;
else
temp1->left=temp;
}
return root;
}
int nth_smallest(struct node *root,int n,int count)
{
if(root->left)
count=nth_smallest(root->left,n,count);
count++;
if(count==n)printf("%d",root->data);
if(root->right)
count=nth_smallest(root->right,n,count);
return count;
}
int del_tree(struct node *root)
{
if(root)
{
del_tree(root->right);
del_tree(root->left);
}
delete root;
return 0;
}
int main()
{
int i,n,d;
printf("enter the number of elements to be inserted into the tree:\n");
scanf("%d",&n);
printf("enter the elements of the tree:\n");
for(i=0;i<n;i++)
{
scanf("%d",&d);
root=bst_ins(root,d);
}
printf("enter the nth smallest number to be searched:\n");
scanf("%d",&n);
nth_smallest(root,n,0);
del_tree(root);
return 0;
}
I also support that O(lgn) solution is not existing, but I try O(k) algorithm and I think I made it, here is my program in c, if there is anything wrong, please let me know about, thanks.
#include<iostream>
using namespace std;
typedef struct node_s {
int value;
struct node_s *left;
struct node_s *right;
}BSTNode, *BSTree;
static int tree_size = 0;
int tree_search(BSTree T, int value, BSTNode **p, BSTNode *f) {
if(!T) {
*p = f;
return 0;
} else {
if(T->value == value) {
*p = T;
return 1;
} else if(value < T->value) {
return tree_search(T->left, value, p, T);
} else {
return tree_search(T->right, value, p, T);
}
}
}
int tree_insert(BSTree *T, int value) {
BSTNode *p = NULL;
if(!tree_search(*T, value, &p, NULL)) {
BSTNode *s = (BSTNode*)malloc(sizeof(BSTNode));
s->value = value;
s->left = NULL;
s->right = NULL;
if(!(*T))
*T = s;
else if(value < p->value)
p->left = s;
else
p->right = s;
return 1;
}
return 0;
}
static int index = 0;
void find_k_th(BSTree T, int k, int *value) {
if(T) {
find_k_th(T->left, k, value);
++index;
if(index == k) {
*value = T->value;
return;
}
find_k_th(T->right, k, value);
}
}
int get_value(BSTree T, int k) {
int k_value = -1;
if(k < 0 || k >= tree_size)
return k_value;
index = 0;
find_k_th(T, k, &k_value);
return k_value;
}
void in_traverse(BSTree T) {
if(T) {
in_traverse(T->left);
cout << T->value << " ";
in_traverse(T->right);
}
}
int main(int argc, char *argv[]) {
int a[] = {5, 9, 13, 4, 6, 7, 34, 12, 25, 16};
int len = sizeof(a) / sizeof(int);
int i;
BSTree T = NULL;
for(i = 0; i < len; i++) {
if(tree_insert(&T, a[i]))
tree_size++;
}
in_traverse(T);
cout << endl;
int k = 4;
cout << get_value(T, k) << endl;
cin.get();
return 0;
}
how about this?
Check for a balanced tree. if not balanced it?? or say cant do in log in
IF it is a balanced tree
Use log N steps to reach the minimum value where N is number of elements
and iteratively find successors till we get the nth smallest element.
This will take log N steps, n times
so O(logN) + O(nlogN) where n is a constant = O(logN)
Assumption: each node holds the number of nodes present within its subtree rooted at that node. If not for this assumption log N is not possible
Node * FindNSmallest(TNode *node, int N) {
if(!node) return NULL;
if(node->left->numNodes+1 == N) return node;
if(node->left->numNodes>=N) return (FindNSmallest(node->left, N);
else return(FindNSmallest(node->right, N-node->left->numNodes-1);
}
can't we solve it by run in order traversal and return on nth step, something like
var step = 0;
var value;
var prevvalue;
var n = 5;
tree.inOrderTraversal(function(node){
if(prevvalue != node.data)
step++;
if(step==n)
value = node.data;
prevvalue = node.data;
});
if(!value)
console.log('not enough nodes');
else
console.log(value);
?
it requires O(n)
maybe the solution only exist for balanced bst where number of nodes = 2^(h+1) - 1 where h is the tree height. the height can be found for log N time by traversing to the left until null node. then we found the subtree which has nth smallest elem( if n <= h+1 then it is in the left subtree we go in order to the left and stop on (h+1 - n) step.
the performance is O(lgN + (h + 1 - n)) = O (lg N * 2 - n) = O(lg N)
What if we do below:
1. Get the number of elements in left subtree in O(log n) time
2. if n < noOfElementInLeftSubtree then recurse in left sub tree
3. if n == noOfElementsInLeftSubtree + 1 then return root
4. else it has to be in right subtree so recurse in right subtree
Solution does not exist. For a log(n) solution, you need to visit each level a constant number of times without traversing all the nodes, effectively eliminating as you go. Elimination is not possible in this case.
- barcod January 19, 2013At the beginning, you are at the root and you can't have any idea where to go. You pick left or right. Without traversing all the nodes in that subtree, you can't even know if you are in the correct subtree. Getting the number of nodes there is already O(n). That's why Log(N) is impossible.
I think this question was meant to be asked for a complete BST.