## Microsoft Interview Question

• 0

Country: United States

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

do a level order traversal, once reached the target node, return next node in the same level if exist.

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

Just realized the question may involve the cousins too. the above solution will not handle that..

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

What is meant by the next sibling? A binary tree can have at most one sibling only.

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

the next right child under the same or diffterent parent but at the same LEVEL

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

Do BFS and keep track of the queue continuously, to figure out if the Target has now been available in the queue. If yes, then find the parent of the target in the queue by continuously dequeing so that the right sibling where ever it is (under same parent of target or different parent) is achieved. Level needs to be tracked because if the target is right most sibling, then the right sibling of it wont exist

``````public class Node {
int value;
public Node left;
public Node right;

public Node(int value) {
this.value = value;
left = null;
right = null;
}

}

import java.util.Scanner;

public class BinaryTree
{
Node root;

BinaryTree()
{
root = null;
}

void insert(int value,int id)
{
Node n = new Node(value);
if(root == null)
{
root = n;
return;
}
Node parent = this.find(root,id/2);
if(id%2==0)
{
parent.left = n;
}
else
parent.right = n;
return;
}

public Node find(Node root, int parent)
{
if (parent==1)
return root;
int level = 1;
int arr[] = new int[100];
int i= parent;
arr[level] = i;
level++;
while(i>1){
i = i/2;
arr[level] = i;
level++;
}
arr[level] = 10101010;
Node temp = root;
for (int j=level-2;j>0;j--)
{
if(arr[j]%2 == 0)
{
//take a left
temp = temp.left;

}
else
{
//take a right;
temp = temp.right;
}
}

return temp;

}

public void buildBinaryTree()
{
System.out.println("Enter the number of nodes");
Scanner s = new Scanner(System.in);
int number = s.nextInt();
for(int i=0;i<number;i++)
{
System.out.println("Enter Node Value");
int value = s.nextInt();
System.out.println("Enter Node ID");
int id = s.nextInt();
insert(value,id);
}

}

public Node findInorder(Node root, int value)
{
Node temp = root;
if(temp == null)
return null;
if(temp.value == value)
{
return temp;
}

Node s = findInorder(temp.left,value);
if(s!=null)
return s;

Node t = findInorder(temp.right,value);
if(t !=null)
return t;
// TODO Auto-generated method stub
return null;
}

public void performInorderTraversal(Node temp)
{

if(temp == null)
return;
performInorderTraversal(temp.left);
System.out.println(temp.value);
performInorderTraversal(temp.right);

}
}

public class QNode
{
int value;
int level;
QNode next;

QNode(int value)
{
this.value = value;
this.next = null;
this.level = 0;
}
}

public class Queue
{
QNode front;
QNode rear;

Queue()
{
front = null;
rear = null;
}

public void enqueue(QNode n)
{
if(front == null)
{
front = rear = n;
return;
}
n.next = front;
front = n;
}

public QNode dequeue()
{
if(front == rear)
{
QNode temp = front;
front = null;
rear = null;
return temp;
}

QNode temp = front;
while(temp != null && temp.next!=rear)
{
temp = temp.next;
}
QNode rtemp = rear;

rear = temp;
rear.next = null;
return rtemp;

}

public boolean elementPresent(int val)
{
QNode temp = front;
while(temp != null)
{
if(temp.value == val)
return true;
temp = temp.next;
}
// TODO Auto-generated method stub
return false;
}

public boolean elementAtFront(int val)
{
if(front.value == val)
return true;
return false;
}
}

import java.util.Scanner;

public class BTreeMain {

public static void main(String[] args)
{
// TODO Auto-generated method stub
BinaryTree b = new BinaryTree();
b.buildBinaryTree();

b.performInorderTraversal(b.root);;
Scanner s = new Scanner(System.in);
System.out.println("Enter the sibling value");
int sibValue = s.nextInt();
Node sibling = b.findInorder(b.root, sibValue);
int x = findNextSibling(b,sibling);
System.out.println("The sibling is : " + x);

}

private static int findNextSibling(BinaryTree b, Node sibling)
{
// TODO Auto-generated method stub
if(sibling == b.root)
{
System.out.println("No sibling for the root");
return -1;
}
Queue q = new Queue();
QNode r = new QNode(b.root.value);
q.enqueue(r);
r.level = 1;
while(q.front != null)
{
QNode y = q.dequeue();

//find using inorder traversal
Node y1 = b.findInorder(b.root,y.value);
Node left = y1.left;
Node right = y1.right;
QNode qleft = null;
QNode qright = null;
if(left != null)
qleft = new QNode(left.value);
if(right != null)
qright = new QNode(right.value);

if(qleft != null)
{
q.enqueue(qleft);
qleft.level = y.level + 1;
}

if(qright != null)
{
q.enqueue(qright);
qright.level = y.level+1;
}

if(q.elementPresent(sibling.value) && !q.elementAtFront(sibling.value))
{
// This implies the sibling is somewhere in the queue
//now keep dequeing the queue to remove x + 1 element
QNode dequeued = null;
while(q.front != null)
{
//keep doing this
dequeued = q.dequeue();
if(dequeued.value == sibling.value)
{
break;
}

}
int l = dequeued.level;
QNode rightSib = q.dequeue();
if(rightSib.level == l)
{
return rightSib.value;
}
else
{
System.out.println("Node is at extreme right cant have sibling");
}

}

}
System.out.println("No sibling exists");
return -1;
}

}``````

CONSOLE OUTPUTS:
===================

Enter the number of nodes
3
Enter Node Value
1
1Enter Node ID

Enter Node Value
2
Enter Node ID
2
Enter Node Value
3
Enter Node ID
3
2
1
3
Enter the sibling value
3
No sibling exists
The sibling is : -1

==================

Enter the number of nodes
9
Enter Node Value
1
Enter Node ID
1
Enter Node Value
2
Enter Node ID
2
Enter Node Value
4
Enter Node ID
4
Enter Node Value
8
Enter Node ID
8
Enter Node Value
17
Enter Node ID
17
Enter Node Value
3
Enter Node ID
3
Enter Node Value
7
Enter Node ID
7
Enter Node Value
14
Enter Node ID
14
Enter Node Value
29
Enter Node ID
29
8
17
4
2
1
3
14
29
7
Enter the sibling value
8
The sibling is : 14

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

Do BFS and keep track of the queue continuously, to figure out if the Target has now been available in the queue. If yes, then find the parent of the target in the queue by continuously dequeing so that the right sibling where ever it is (under same parent of target or different parent) is achieved. Level needs to be tracked because if the target is right most sibling, then the right sibling of it wont exist

``````public class Node {
int value;
public Node left;
public Node right;

public Node(int value) {
this.value = value;
left = null;
right = null;
}

}

import java.util.Scanner;

public class BinaryTree
{
Node root;

BinaryTree()
{
root = null;
}

void insert(int value,int id)
{
Node n = new Node(value);
if(root == null)
{
root = n;
return;
}
Node parent = this.find(root,id/2);
if(id%2==0)
{
parent.left = n;
}
else
parent.right = n;
return;
}

public Node find(Node root, int parent)
{
if (parent==1)
return root;
int level = 1;
int arr[] = new int[100];
int i= parent;
arr[level] = i;
level++;
while(i>;1){
i = i/2;
arr[level] = i;
level++;
}
arr[level] = 10101010;
Node temp = root;
for (int j=level-2;j>;0;j--)
{
if(arr[j]%2 == 0)
{
//take a left
temp = temp.left;

}
else
{
//take a right;
temp = temp.right;
}
}

return temp;

}

public void buildBinaryTree()
{
System.out.println("Enter the number of nodes");
Scanner s = new Scanner(System.in);
int number = s.nextInt();
for(int i=0;i<number;i++)
{
System.out.println("Enter Node Value");
int value = s.nextInt();
System.out.println("Enter Node ID");
int id = s.nextInt();
insert(value,id);
}

}

public Node findInorder(Node root, int value)
{
Node temp = root;
if(temp == null)
return null;
if(temp.value == value)
{
return temp;
}

Node s = findInorder(temp.left,value);
if(s!=null)
return s;

Node t = findInorder(temp.right,value);
if(t !=null)
return t;
// TODO Auto-generated method stub
return null;
}

public void performInorderTraversal(Node temp)
{

if(temp == null)
return;
performInorderTraversal(temp.left);
System.out.println(temp.value);
performInorderTraversal(temp.right);

}
}

public class QNode
{
int value;
int level;
QNode next;

QNode(int value)
{
this.value = value;
this.next = null;
this.level = 0;
}
}

public class Queue
{
QNode front;
QNode rear;

Queue()
{
front = null;
rear = null;
}

public void enqueue(QNode n)
{
if(front == null)
{
front = rear = n;
return;
}
n.next = front;
front = n;
}

public QNode dequeue()
{
if(front == rear)
{
QNode temp = front;
front = null;
rear = null;
return temp;
}

QNode temp = front;
while(temp != null && temp.next!=rear)
{
temp = temp.next;
}
QNode rtemp = rear;

rear = temp;
rear.next = null;
return rtemp;

}

public boolean elementPresent(int val)
{
QNode temp = front;
while(temp != null)
{
if(temp.value == val)
return true;
temp = temp.next;
}
// TODO Auto-generated method stub
return false;
}

public boolean elementAtFront(int val)
{
if(front.value == val)
return true;
return false;
}
}

import java.util.Scanner;

public class BTreeMain {

public static void main(String[] args)
{
// TODO Auto-generated method stub
BinaryTree b = new BinaryTree();
b.buildBinaryTree();

b.performInorderTraversal(b.root);;
Scanner s = new Scanner(System.in);
System.out.println("Enter the sibling value");
int sibValue = s.nextInt();
Node sibling = b.findInorder(b.root, sibValue);
int x = findNextSibling(b,sibling);
System.out.println("The sibling is : " + x);

}

private static int findNextSibling(BinaryTree b, Node sibling)
{
// TODO Auto-generated method stub
if(sibling == b.root)
{
System.out.println("No sibling for the root");
return -1;
}
Queue q = new Queue();
QNode r = new QNode(b.root.value);
q.enqueue(r);
r.level = 1;
while(q.front != null)
{
QNode y = q.dequeue();

//find using inorder traversal
Node y1 = b.findInorder(b.root,y.value);
Node left = y1.left;
Node right = y1.right;
QNode qleft = null;
QNode qright = null;
if(left != null)
qleft = new QNode(left.value);
if(right != null)
qright = new QNode(right.value);

if(qleft != null)
{
q.enqueue(qleft);
qleft.level = y.level + 1;
}

if(qright != null)
{
q.enqueue(qright);
qright.level = y.level+1;
}

if(q.elementPresent(sibling.value) && !q.elementAtFront(sibling.value))
{
// This implies the sibling is somewhere in the queue
//now keep dequeing the queue to remove x + 1 element
QNode dequeued = null;
while(q.front != null)
{
//keep doing this
dequeued = q.dequeue();
if(dequeued.value == sibling.value)
{
break;
}

}
int l = dequeued.level;
QNode rightSib = q.dequeue();
if(rightSib.level == l)
{
return rightSib.value;
}
else
{
System.out.println("Node is at extreme right cant have sibling");
}

}

}
System.out.println("No sibling exists");
return -1;
}

}``````

CONSOLE OUTPUTS:
===================

Enter the number of nodes
3
Enter Node Value
1
1Enter Node ID

Enter Node Value
2
Enter Node ID
2
Enter Node Value
3
Enter Node ID
3
2
1
3
Enter the sibling value
3
No sibling exists
The sibling is : -1

==================

Enter the number of nodes
9
Enter Node Value
1
Enter Node ID
1
Enter Node Value
2
Enter Node ID
2
Enter Node Value
4
Enter Node ID
4
Enter Node Value
8
Enter Node ID
8
Enter Node Value
17
Enter Node ID
17
Enter Node Value
3
Enter Node ID
3
Enter Node Value
7
Enter Node ID
7
Enter Node Value
14
Enter Node ID
14
Enter Node Value
29
Enter Node ID
29
8
17
4
2
1
3
14
29
7
Enter the sibling value
8
The sibling is : 14

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

node* nextRight(bst *root, int key)
{
if(root == NULL)
return NULL;

queue<node*> nodeQ;
queue<int> levelQ;

int level = 0;
nodeQ.push(root);
levelQ.push(level);

while(!nodeQ.empty())
{
root = nodeQ.front();
nodeQ.pop();
level = levelQ.front();
levelQ.pop();

if(root->data == key)
{
if(levelQ.size() == 0 || levelQ.front() != level)
return NULL;
return nodeQ.front();
}
if(root->left)
{
nodeQ.push(root->left);
levelQ.push(level+1);
}
if(root->right)
{
nodeQ.push(root->right);
levelQ.push(level+1);
}
}
return NULL;
}

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

``````#include <iostream>
using namespace std;

struct node {
int val;
node *left, *right;
};

node *createnode(int val) {
node *n = new node;
n->val = val;
n->left = n->right = nullptr;
return n;
}

node* findsib(node *root, int lev) {
if(root == nullptr)
return nullptr;
if(lev == 0)
return root;
node *ret = findsib(root->left, lev - 1);
if(ret == nullptr)
ret = findsib(root->right, lev - 1);
return ret;
}

int util(node *root, node *target, node* (&sib)) {
if(root == nullptr)
return -1;
if(root == target) {
return 1;
}
int ret = util(root->left, target, sib);
if(ret != -1) {
if(sib == nullptr) {
sib = findsib(root->right, ret- 1);
}
return ret + 1;
}
ret = util(root->right, target, sib);
if(ret != -1) {
if(sib == nullptr) {
sib = findsib(root->left, ret - 1);
}
ret + 1;
}
return -1;
}

node *Find(node *root, node* target) {
if(target == nullptr)
return nullptr;
node *sib = nullptr;
util(root, target, sib);
return sib;
}

int main() {
node *root = createnode(1);
root->left = createnode(2);
root->right = createnode(3);
root->right->right = createnode(10);
root->left->left = createnode(4);
//root->left->right = createnode(5);
node *target = root->left->left;
node *sib = Find(root, target);
if(sib)
cout << "Target node = " << sib->val;
return 0;
}``````

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

``````Node FindSibling( Node root, Node target )
{
if(node.left == target )
return node.right;
else if( node.right == target )
return node.left;

Node foundSibling = FindSibling( node.left, target );
if( foundSibling )
return foundSibling;

foundSibling = FindSibling( node.right, target );
if( foundSibling )
return foundSibling;

return null;
}``````

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

3
/ \
2 6
/ \
1 7

What if target is 1 ?

Comment hidden because of low score. Click to expand.
-2

@glebstepanov1992 I changed the tree construction part to match your example:

``````Node l2leftright = new Node(null, null, 7);
Node l2leftleft = new Node(null, null, 1);

// level 1
Node l1right = new Node(null, null, 6);
Node l1left = new Node(l2leftleft, l2leftright, 2);

// level 0 - root
Node root = new Node(l1left, l1right, 3);``````

Ans is 7.

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.