Are two Binary Trees identical

Write a program to verify whether two Binary Trees identical or not.

Solution:

using System;
using System.Collections.Generic;

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

            var bt2 = new BinaryTree<int>();
            bt2.Root = new Node<int>(1);
            bt2.Root.Left = new Node<int>(2);
            bt2.Root.Right = new Node<int>(3);
            bt2.Root.Left.Left = new Node<int>(4);
            bt2.Root.Right.Left = new Node<int>(5);
            bt2.Root.Right.Right = new Node<int>(6);

            Console.WriteLine(BinaryTree<int>.AreTreesIdentical(bt1.Root, bt2.Root)
                ? "Trees are identical"
                : "Trees are not identical");

            Console.ReadLine();
        }
    }

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

        public BinaryTree()
        {
            Root = null;
        }

        public static bool AreTreesIdentical(Node<T> root1, Node<T> root2)
        {
            if (root1 == null && root2 == null)
                return true;

            if (root1 != null && root2 != null)
            {

                return root1.Data.Equals(root2.Data) &&
                       AreTreesIdentical(root1.Left, root2.Left) &&
                       AreTreesIdentical(root1.Right, root2.Right);
            }

            return false;
        }
    }


    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 *