## Microsoft Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 10 vote

Carry out a Level Order Traversal and once you get the node that is given, the very next node would be the left most right cousin.

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

that can be the sibling also ... we need to check for that in this solution

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

This is a solution but not optimum one,

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

@sonesh
I think this answer works well.
What do you mean that this not the optimal one?
Could you show me the optimal one?

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

The proposed solution will work for BT. Solution is not utilizing the fact that it is a BST.

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

Just traverse till left most node,when you hit null,go to the root node of the current node and then go for its right child.

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

you are also given a *node*, you need to tell left most right cousin of that given node only.

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

what if the the given node does not have any child i mean the given node is itself a leaf node.then ??

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

@ravi : it can be , then also it many have right cousin, you need to find left most, but there are some element which don't have, you have to say no in minimum number of steps not just in order but in actual step counting

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

once you traverse down those are not cousin those are child so cousin should be in the same level but left most right cousin dint make any sense please help me to understand the question

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

i think it means its immediate right cousin :)

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

if so then find the parent node by search and find the next sibling i.e leftmost right cousin

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

yes, it means immediate right cousin, but a parent node might not have right node, then ??

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

is it leftmost right cousin in same level ?

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

that is what cousin mean, it will be at same level

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

Hi!

I would mark the empty nodes with some standard value. And than do a BFS : when I reach the level with the given data , I will check for the left most right position which should be the cousin .. and if it is a standard value of mine then return null else return the data from the node.
(Correct. I mean BFS)

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

Doing BST means nothing, BST is binary search tree, doing it make no sense. anyway, even if you make it complete by adding additional nodes with some value. then also it does not give correct answer, and one more thing you actually didn't tell us how do you check for left most right cousin, actually that is the question ??
if you just check right node, then that may not be the answer for example

...............8
............../...\
............3....4
.........../........\
.........5..........9
Leftmost right cousin of 5 is 9, and of 3 is 4 and and of 9 is no one.

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

@sonesh What I understand from left most right cousin is that the node that we need to find should not be the child of the parent of the given node, that means in your example above, left most right cousin of 3 is not 4, because siblings are literally not cousins. Cousins mean the nodes at the same level but not the children of the same parent. Hence 9 is a cousin of 5.

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

@Messiah :
Yes you are right, actually interviewer define like that,
he first write a simple example and then says that this is the answer and we call this type of problem as left most right cousin problem.
so from their only i have given the example, actually he want to know the left most node of same depth.

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

I think Kamy means a BFS.

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

I may not be sure, but the following part worked with one example at least. I didn't have time to testit with other examples. It is basically BFS.

Structure of the binary search tree used modified for BFS

``````typedef struct bsearch_tree
{
int key;
int level;
struct bsearch_tree *parent;
struct bsearch_tree *left;
struct bsearch_tree *right;
}BSTREE;``````

The function

``````BSTREE* leftmost_right_cousin(BSTREE* T,int item)
{
QUEUE Q;
BSTREE *u,*this_parent;
int find=0,find_level;
if(T!=NULL)
{
init_queue(&Q);
T->level = 0;
enqueue(&Q,T);
while(!is_empty(&Q))
{
u = dequeue(&Q);
if(find) //we have found the node whose cousin we are trying to find
{
if(u->level==find_level && u->parent != this_parent) //the cousin will be in the same level of the tree but its parent will be different
return u; //return the first node satisfying the condition
else if(u->level > find_level) //we are looking at some node at a deeper level than the required node. So we must not have found any cousin (to the right of the given node and having a different parent)
return NULL;
}
if(u->key == item) //found the node whose cousin we are looking for
{ find = 1; find_level = u->level; this_parent = u->parent;}
if(u->left!=NULL)
{
u->left->level = u->level + 1; //basic BFS algo, Since left node is put first into Q and Q being FIFO we will be dequeuing nodes from left to right in a particular level
u->left->parent = u;
enqueue(&Q,u->left);
}
if(u->right!=NULL)
{
u->right->level = u->level + 1;
u->right->parent = u;
enqueue(&Q,u->right);
}
}
return NULL; //we didn't find the node whose cousin we are looking for, so the given node doesn't exist in the first place
}
return NULL; //the tree has no nodes at all
}``````

As already stated in the comment, since we are using a Queue in BFS and we are enquing nodes from left to right in a particular level, I don't think we will require to mark the nodes Left or Right, doing which will actually require different implementations for the given node being Left/Right.

*The fn provided is subject to correction.

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

This is a question for Binary Search Tree.
So, we should make use of this fact.

Pseudocode::

**Do a binary Search to find the given node.
**Keep Track of a previous ancestor which has a right child and its level.
**If given node was a left child, its parent's right child will be its immediate right sibling,
**otherwise, its ancestor's right_child's leftmost node at the level of the given node will be its immediate right sibling.

Max Time: O(2*logn)
Space: O(1)

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

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

First of all I would like to tell you that the question is for a binary tree, The interviewer just say that the binary tree is given.
your algorithm is correct for BST, but need modifications so that others can also understand. check the cases when we don't have right children, or our node itself is a right children of a node, does the complexity you have stated is correct,
try to think an example when the complexity can go upto O(n).
for your understanding there is nothing like O(2logn), it is O(logn).

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

Sonesh,
In your question you have mentioned Binary Search Tree. you might want to update the question.

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

@ Sonesh,can we modify the node structure? Can we add one extra sibling pointer?

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

O(N) worst case. O(N) space.

1. BFS (left to right), using a queue and inserting empty node marker in the queue when a node is missing a child and a level marker when we hit a new level.

2. If we find the value, its cousin must be behind it in the queue and be before the next level marker. If it's an even node (counting from left) its first cousin is at least two nodes way. Otherwise its next node is at least one node away.

3. Pop off the queue until we find the next non empty cousin (return it) or we hit the level marker (return null).

This is somewhat complex and probably not optimal but it's the best I can come up with.

``````public Node getLeftmostRightCousin(int val) {
if(root == null) {
return null;
}

int curNodeFromLeft = 0;
Node levelMarker = new Node(-1);
Node emptyNodeMarker = new Node(-1);
boolean nextLevelEmpty = true;

while(!nodeQueue.isEmpty()) {
Node curr = nodeQueue.remove();

if(curr == levelMarker) {
if(nextLevelEmpty) {
return null; // No more real nodes on the next level.
}
if(!nodeQueue.isEmpty()) {
}

curNodeFromLeft = 0; // starting a new level
nextLevelEmpty = true;
continue;
}

// Find its nearest cousin!
if(curr.value == val) {
if(curNodeFromLeft % 2 == 0)  { // even node is left child. Next cousin is min two nodes to the right.
nodeQueue.remove();
}

// Remove from the queue until we hit the first real node; that's our closest right cousin.
while((nodeQueue.peek() == emptyNodeMarker) && (!nodeQueue.isEmpty())) {
nodeQueue.remove();
}

if(!nodeQueue.isEmpty()) {
if(nodeQueue.peek() != levelMarker) {
return nodeQueue.remove();
}
}

return null;
}

if(curr.left != null) {
nextLevelEmpty = false;
} else {
}

if(curr.right != null) {
nextLevelEmpty = false;
} else {
}

curNodeFromLeft++;
}

return null;
}``````

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

Actually it's O(logn) space. It will store, at maximum number of nodes at deepest level in the queue.

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

Here is my implementation using Java:

``````public static Node leftMostRight(Node root, Node target){
if(root == null || isLeaf(root) || target == null)
return null;
Queue<Node> nodeQ = new ArrayDeque<Node>();
boolean findTarget = false;
nodeQ.offer(root);
Queue<Integer> levelQ = new ArrayDeque<Integer>();
levelQ.offer(1);
int targetLevel=0;
while(!nodeQ.isEmpty()){
Node node = nodeQ.poll();
int currentLevel = levelQ.poll();
if(findTarget && target.parent != node.parent && currentLevel == targetLevel)
return node;
if(node.value == target.value){
findTarget = true;
targetLevel = currentLevel;
}
if(node.left != null){
nodeQ.offer(node.left);
levelQ.offer(currentLevel+1);
}
if(node.right != null){
nodeQ.offer(node.right);
levelQ.offer(currentLevel+1);
}
}
return null;
}``````

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

``````private static Node nextRight(Node root, int i) {
Queue<Node> q1=new ArrayDeque();
Queue<Node> q2=new ArrayDeque();
while(!q1.isEmpty()){

Node value=q1.remove();
if(value.data==i){
return q1.remove();
}
else{
}
if(q1.isEmpty()){
q1=q2;
q2=new ArrayDeque<Node>();
}

}
return null;

}``````

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

1. Keep a pointer to grand parent of the node being searched.
2. After that easy to find the sibling of the parent and if they have any child nodes.

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

1. Find the node with the searched value for using the regular BST node lookup. Also look for the first time the branching happens for the left and start counting the nodes thereafter.
(If there is no branching, there can't be any next sibling)
2. If branching occurs again, keep a note of the node and reset count
3. The count is the distance b/w the LCA (at the location where branching occurred) of the sibling and the searched value.

4. Knowing the LCA node, start DFS until the depth traversed == count (from last step).

``````class Node(object):

def __init__(self, data):
self.left = None
self.right = None
self.data = data

def findcommonNode(node, val):

isLeft = True

nodeP = None
count = 0

while node != None:

if node.data == val and isLeft:
return nodeP, count
if val < node.data :
if node.right:
nodeP = node
count = 0
isLeft = True
node = node.left
else:
node = node.right
count += 1

return None, count

def nextSibling(node, i, count):

if not node:
return None
if i == count:
return node

if node.left:
node = nextSibling(node.left, i+1, count)
elif node.right:
node = nextSibling(node.right, i+1, count)

return node

def findNextSibling(root, val):

pNode, count = findcommonNode(root, 7)
if pNode:
sNode = nextSibling(pNode.right, 1, count)

return sNode.data if sNode else None``````

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

``````1) Find the node, and keep track of level (say target node is found on level L)- time log N
2) Push each traversed node into a stack
3) When node is found
a) Pop the stack to remove the parent of the target node
b) If stack is empty then given node does not have a cousin; return
c) Do DFS from the right child of the current top of the stack (which is the grand-parent of the target node) and return the first node at Level L``````

Time complexity is log N, space complexity log N

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

1. Do BFS right left.
2. Maintain a pointer to the previous element
3. Once the node is found, the previous element is the left most right child if and only if the key of the previous element is bigger than that of the node. If not there is no right sibling.

Space - O(log n)
time - O(n)

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

1. Find the root of the given "node" [ long n]. While doing so keep a track of the parent node.
2. Once found. Run a In-order traversal from the parent node found in step 1.
3. The first leaf node in the in-order traversal would be left-most right cousin.
time-complexity [ O(logN)

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

Why do you say that the left most right cousin would be a leaf node?
How do you guarantee that you would find the cousin node if you run inorder traversal from parent node of the given node

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

@messiah, i meant the first node with no-more left sub-tree to be the left-most right cousin. My mistake, this would not necessarily be the leaf node.

To my understanding: To reach the left most right cousin, you need to explore the entire right sub-tree of the given node's parent. (This helps me find the 'right' cousin). Further, in this right sub-tree we are interested in finding the left most node, which can be reached by exploring the left subtree, hence in-order. If you look at such a subtree, the left most (visual node)is always reachable through inorder traversal.

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

your first step says that find the node from the root node, as because root node is given, we don't have to find it. and while doing do keep track of the parent node, means we store parent node in an array, or if we are in recursion then when we back trace then we can again access them.
your second step says that start inorder traveling from root node not from parent node, (obviously because see the example which i have given in kamy's post) or you mean to say that we start inorder traveling from all parents starting from the parent node of the given node to grand paren node and uoto root node,

look at this example :
..............8
........../........\
........9........10
....../..\......../...\
...11...3....4....6
.....\....\...../.\..../
......7...1.2..5.12

now call LeftMostRightCousin : LMRC
LMRC are following
elt : their LMRC's
8 : none
9 : 10;
10 ; none;
11 : 3;
3 : 4;
4 : 6;
6 : none;
7 : 1;
1 : 2;
2 : 5;
5 : 12;
12 : none
now think that is your algorithm correct ?

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

he said he already gave a BST, He obviously gives it in an array..!!Confirm from the interviewer that its accepted in In-order only

1.)Search for the Required node in the Array (which if found say is at i ),
2.)Nodes From (i+1---till---2i) are its Cousins

Hopefully im right!!!!

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

if he particularly insists no i want even the implementation of the tree in IN-order show it...!!
then do an inorder Traversal of the tree store it in an array and do accordingly as stated above

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

please follow the example which I have given in comments on @skp post, you will understand the question.

Comment hidden because of low score. Click to expand.

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.