|
192. Write an Algorithm for Finding Siblings in a Binary Search Tree.
Microsoft Interview Questions and Answers
(Continued from previous question...)
192. Write an Algorithm for Finding Siblings in a Binary Search Tree.
Question:
Write an Algorithm for Finding Siblings in a Binary Search Tree.
maybe an answer:
using System;
using System.Diagnostics;
using System.Collections.Generic;
using System.Text;
namespace MSIntervewPreparation
{
class TreeNode
{
public int Data { get; set; }
public TreeNode Left { get; set; }
public TreeNode Right { get; set; }
public TreeNode Sibling { get; set; }
public TreeNode(int data)
{
this.Data = data;
this.Left = null;
this.Right = null;
this.Sibling = null;
}
}
class Tree
{
public TreeNode Root { get; set; }
public Tree()
{
}
public void FindSiblings(TreeNode node)
{
Queue<TreeNode> q = new Queue<TreeNode>();
q.Enqueue(node);
TreeNode previous = null;
TreeNode current = null;
while (q.Count > 0)
{
current = q.Dequeue();
if (current.Left != null)
{
q.Enqueue(current.Left);
}
if (current.Right != null)
{
q.Enqueue(current.Right);
}
if (previous != null && previous.Data < current.Data)
{
previous.Sibling = current;
Console.WriteLine(previous.Data + " : " + previous.Sibling.Data);
}
previous = current;
}
}
public void InsertNode(int data)
{
if (Root == null)
{
Root = new TreeNode(data);
}
else
{
TreeNode current = Root;
while (current != null)
{
if (data <= current.Data)
{
// InsertNode left
if (current.Left == null)
{
current.Left = new TreeNode(data);
return;
}
else
{
current = current.Left;
}
}
else
{
// InsertNode right
if (current.Right == null)
{
current.Right = new TreeNode(data);
return;
}
else
{
current = current.Right;
}
}
}
}
}
}
class Program
{
static void Main(string[] args)
{
Tree binaryTree = new Tree();
binaryTree.InsertNode(8);
binaryTree.InsertNode(4);
binaryTree.InsertNode(2);
binaryTree.InsertNode(6);
binaryTree.InsertNode(1);
binaryTree.InsertNode(3);
binaryTree.InsertNode(5);
binaryTree.InsertNode(7);
binaryTree.InsertNode(12);
binaryTree.InsertNode(10);
binaryTree.InsertNode(14);
binaryTree.InsertNode(9);
binaryTree.InsertNode(11);
binaryTree.InsertNode(13);
binaryTree.InsertNode(15);
Console.WriteLine("\n Find All Siblings... ");
binaryTree.FindSiblings(binaryTree.Root);
Console.ReadLine();
}
}
}
(Continued on next question...)
Other Interview Questions
| 