# Convert Binary Tree to Binary Search Tree.

Write a program to convert Binary Tree to Binary Search Tree

#### Solution:

``````using System;

namespace Pattern
{
class Program
{
//Represent a node of binary tree
public static void Main()
{
var bt = new BinarySearchTree<int>();
bt.Root = new Node<int>(1);
bt.Root.Left = new Node<int>(2);
bt.Root.Right = new Node<int>(3);
bt.Root.Left.Left = new Node<int>(4);
bt.Root.Left.Right = new Node<int>(5);
bt.Root.Right.Left = new Node<int>(6);
bt.Root.Right.Right = new Node<int>(7);

Console.WriteLine("Binary tree: ");
bt.PrintTree(bt.Root);

var bst = bt.Convert(bt.Root);
Console.WriteLine();
Console.WriteLine("Binary search tree: ");
bt.PrintTree(bst);
}
}

public class BinarySearchTree<T>
{
public Node<T> Root;

T[] _arr;
int _index;

public BinarySearchTree()
{
Root = null;
}

public Node<T> Convert(Node<T> node)
{
var treeSize = CalculateSize(node);
_arr = new T[treeSize];

ConvertToArray(node);
Array.Sort(_arr);
var d = CreateBinarySearchTree(0, _arr.Length - 1);
return d;
}

int CalculateSize(Node<T> node)
{
if (node == null)
return 0;

return CalculateSize(node.Left) + CalculateSize(node.Right) + 1;
}

public void ConvertToArray(Node<T> node)
{
if (Root == null)
{
Console.WriteLine("Tree is empty");
return;
}

if (node.Left != null)
ConvertToArray(node.Left);

_arr[_index] = node.Data;
_index++;
if (node.Right != null)
ConvertToArray(node.Right);
}

public Node<T> CreateBinarySearchTree(int start, int end)
{
if (start > end)
return null;

var mid = (start + end) / 2;
var node = new Node<T>(_arr[mid])
{
Left = CreateBinarySearchTree(start, mid - 1),
Right = CreateBinarySearchTree(mid + 1, end)
};

return node;
}

public void PrintTree(Node<T> node)
{
if (Root == null)
{
Console.WriteLine("Tree is empty");
return;
}

if (node.Left != null)
PrintTree(node.Left);
Console.Write(node.Data + "\t");
if (node.Right != null)
PrintTree(node.Right);
}
}

public class Node<T>
{
public T Data;
public Node<T> Left;
public Node<T> Right;

public Node(T data)
{
Data = data;
Left = null;
Right = null;
}
}
}
``````