## Microsoft Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**In-Person

@sonesh

I think this answer works well.

What do you mean that this not the optimal one?

Could you show me the optimal one?

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.

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

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

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

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

Hi!

What about a BFS?

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)

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.

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

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

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.

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)

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

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;
Queue<Node> nodeQueue = new LinkedList<Node>();
Node levelMarker = new Node(-1);
Node emptyNodeMarker = new Node(-1);
boolean nextLevelEmpty = true;
nodeQueue.add(root);
nodeQueue.add(levelMarker);
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()) {
nodeQueue.add(levelMarker);
}
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) {
nodeQueue.add(curr.left);
nextLevelEmpty = false;
} else {
nodeQueue.add(emptyNodeMarker);
}
if(curr.right != null) {
nodeQueue.add(curr.right);
nextLevelEmpty = false;
} else {
nodeQueue.add(emptyNodeMarker);
}
curNodeFromLeft++;
}
return null;
}
```

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

```
private static Node nextRight(Node root, int i) {
Queue<Node> q1=new ArrayDeque();
Queue<Node> q2=new ArrayDeque();
q1.add(root);
while(!q1.isEmpty()){
Node value=q1.remove();
if(value.data==i){
return q1.remove();
}
else{
if(value.left!=null) q2.add(value.left);
if(value.right!=null) q2.add(value.right);
}
if(q1.isEmpty()){
q1=q2;
q2=new ArrayDeque<Node>();
}
}
return null;
}
```

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

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

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)

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

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

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,

Your 3rd step is wrong.

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 ?

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!!!!

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

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.

- Messiah January 04, 2013