Binary Tree

Write a program to implement Binary Tree using the linked list

Solution

using System;
using System.Collections.Generic;

namespace Pattern
{
    class Program
    {
        //Represent a node of binary tree  
        public static void Main()
        {
            var bt = new BinaryTree<int>();
            bt.AddNode(1);
            bt.AddNode(2);
            bt.AddNode(3);
            Console.WriteLine("Binary Tree");
            bt.Print(bt.Root);
            bt.AddNode(4);
            Console.WriteLine();
            Console.WriteLine("Added new item to binary tree");
            bt.Print(bt.Root);
            Console.ReadLine();
        }
    }

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

        public BinaryTree()
        {
            Root = null;
        }

        public void AddNode(T data)
        {
            var newNode = new Node<T>(data);

            if (Root == null)
            {
                Root = newNode;
                return;
            }

            var queue = new Queue<Node<T>>();
            queue.Enqueue(Root);

            while (true)
            {
                var node = queue.Dequeue();
                if (node.Left != null && node.Right != null)
                {
                    queue.Enqueue(node.Left);
                    queue.Enqueue(node.Right);
                }
                else
                {
                    if (node.Left == null)
                    {
                        node.Left = newNode;
                        queue.Enqueue(node.Left);
                    }
                    else
                    {
                        node.Right = newNode;
                        queue.Enqueue(node.Right);
                    }
                    break;
                }
            }
        }

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

            if (node.Left != null)
                Print(node.Left);
            Console.Write(node.Data + " ");
            if (node.Right != null)
                Print(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;
        }
    }
}