Bhavya

Code -> Break -> Fix -> Blog

List duplicates in a given Binary Search Tree

Leave a comment

Problem : List all duplicates in a given Binary Search Tree

Assumptions :

1. All “less than” values goes to the LEFT.

2. All “greater than or equal to” values goes to the RIGHT.

List : 5, 3, 10, 5, 4, 3, 7, 5, 5, 5, 2, 4, 10, 8, 10, 5

Output : 3, 4, 5, 5, 5, 5, 5, 10, 10


internal class BST
{
public int Data;
public BST Left;
public BST Right;
}

internal class Program
{
static int lastData;

public static void Main()
{
var root = BuildTree(5, 3, 10, 5, 4, 3, 7, 5, 5, 5, 2, 4, 10, 8, 10, 5);

Console.WriteLine("Duplicate List");
ListDuplicate(root);

Console.ReadLine();
}

private static BST BuildTree(params int[] list)
{
BST temp = null;
BST root = null;

foreach (var l in list)
{
temp = root;
BST node = new BST();
node.Data = l;
node.Left = null;
node.Right = null;

if (temp == null)
{
temp = node;
root = node;
}
else
{
while (temp != null)
{
if (l < temp.Data)
{
if (temp.Left == null)
{
temp.Left = node;
break;
}

temp = temp.Left;
}
else
{
if (temp.Right == null)
{
temp.Right = node;
break;
}

temp = temp.Right;
}
}
}
}

return root;
}

private static void ListDuplicate(BST root)
{
if (root == null)
{
return;
}

ListDuplicate(root.Left);

if (lastData == root.Data)
{
Console.WriteLine(root.Data);
}

lastData = root.Data;

ListDuplicate(root.Right);

}
}

~BS

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s