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);
            Console.ReadLine();
        }
    }

    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;
        }
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *