CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Microsoft Interview Question


Country: United States
More Questions from This Interview



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.

- Vin December 18, 2013 | Flag Reply
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..

- sva December 15, 2013 | Flag Reply
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.

- Codac December 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- devball December 22, 2013 | Flag
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
		//Perform Breadth first traversal
		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

- Anonymous December 22, 2013 | Flag Reply
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
		//Perform Breadth first traversal
		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

- devball December 22, 2013 | Flag Reply
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;
}

- Rakesh Mondal August 04, 2014 | Flag Reply
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() {
	// your code goes here
	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;
	else cout << "Not found";
	return 0;
}

- rishab99999 April 15, 2015 | Flag Reply
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;
}

- sva December 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

3
/ \
2 6
/ \
1 7

What if target is 1 ?

- glebstepanov1992 December 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

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

- thelineofcode December 17, 2013 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More