## Microsoft Interview Question for Software Engineer / Developers

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

4cases
root->left->left/right==target
root->right->left/right==target

it(T==NULL)
return;
if(T->left && T->left->left==target)
cout<<"Next largest"<<T->left->value;
else if(T->left && T->left->right==target)
cout<<"Next largest"<<T->value;
else if(T->right && T->right->left==target)
cout<<"Next largest"<<T->right->value;
else if(T->right && T->right->right==target)
cout<<"Next largest"<<T->value;
else
func(T->left,target);
func(T->right,target);

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

logan: tree is not BST

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

We can do an inorder traversal as follows:

``````Node GetNextLargest(Node* node)
{
if(NULL==node)
return NULL;
if(node->right)
{
node=node->right;
if(node->left)
node=(node->left);
}
if(node->parent)
{
if(node==node->parent->left)
return (node->parent);
else
{
while(node->parent)
{
if(node==node->parent->left)
return node->parent;
else
node=node->parent;
}
}
}
return NULL;
}``````

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

If the given tree is a BST then the second solution posted above is right. But since it has just been provided as a Binary tree i dont think we can use that solution.
@Laks: Inorder traversal is just a method of printing out nodes, since we can assume the Binary tree to be ordered in any particular manner.. i dont think simply doing a inorder traversal would give the result.
A brute force approach i can think of ;)
- Do a traversal and store the values of all nodes in an array - O(n)
- Find the next higher element by making a one pass through the array-
O(n)
Val : = value of node given to us .. whose higher noder we have to find
Big : value of the next bigger node set to 0
for( i from 1 to n)
{
if (array[i] > Val)
{
if(array[i] < Big)
Big = array[i]
}
}
- Traverse the tree looking for the node having the value of Big and return O(n)

Maybe the whole thing can be accomplished by 2 Traversals too minus the temp array
Do a traversal and find value of Big
Do a traversal and get node corresponding to Big

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

bullsh*t: if binary tree is not BST then the whole problem does not make any sense:
it's just "find the next biggest value in an array"

@anonymous: what if the tree structure does not provide a 'parent pointer' ?

here is a simple solution:

struct bin_tree {
bin_tree *left;
bin_tree *right;
int n;
};

int next_biggest(bin_tree *t, int val) {

if(t == 0)
return -1;
if(val < t->n) {
c = next_biggest(t->left, val);
if(c != -1)
return c;
return t->n;
}
return next_biggest(t->right, val);
}

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

Inorder search the tree.
VAL current next largest value.
If node->value > GIVEN_VALUE && less than VAL
VAL = node->value;
return VAL;

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

Using any of the traversal algorithms, keep track of max1 and max2 (max1 = maximum node in the tree).

When you encounter a new node, you compare it with max1 first, and if the node is bigger you move max1 to max2. Or if it's smaller, compare it with max2 also.
Here is my implementation.

``````#include <stdio.h>
#include <stdlib.h>

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/*Function protoypes*/
void printGivenLevel(struct node* root, int level, int *max1, int *max2);
int height(struct node* node);
struct node* newNode(int data);

/* Function to print level order traversal a tree*/
void printLevelOrder(struct node* root)
{
int h = height(root);
int i,max1=0,max2=0;
for(i=1; i<=h; i++)
printGivenLevel(root, i,&max1,&max2);

printf("max 1 :%d, max2 :%d",max1,max2);
}

/* Print nodes at a given level */
void printGivenLevel(struct node* root, int level, int *max1, int *max2)
{

if(root == NULL)
return;
if(level == 1)
{
printf("%d ", root->data);

if(root->data > *max1)
{
*max2 = *max1;
*max1 = root->data;
}
else if(root->data > *max2)
*max2 = root->data;

}

else if (level > 1)
{
printGivenLevel(root->left, level-1,max1,max2);
printGivenLevel(root->right, level-1,max1,max2);
}
}

/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(struct node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the height of each subtree */
int lheight = height(node->left);
int rheight = height(node->right);

/* use the larger one */
if (lheight > rheight)
return(lheight+1);
else return(rheight+1);
}
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/* Driver program to test above functions*/
int main()
{
struct node *root = newNode(100);
root->left        = newNode(21);
root->right       = newNode(32);
root->left->left  = newNode(4);
root->left->right = newNode(5);

printf("Level Order traversal of binary tree is \n");
printLevelOrder(root);

getchar();
return 0;
}``````

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

To find the next largest node look at the right subtree of the node. The leftmost leaf in the right subtree will be the next successor (or the next largest node). If there is no right subtree then move up till the current node is left child of it's parent, the parent then forms the next successor.

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

Is it not a BST

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

Can we do an inorder traversal of the tree and look for the node with the given value. The node that is after printed this node is the next largetst node since an inorder traversal gives us a sorted list.
Let me know if this is possible.

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.