DataStructures/CheckIfTreesAreIdenticalIterative at master · pyusha1006/DataStructures · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
package com.ques.array;

import java.util.*;				//Time complexity:O(n + m)
class Node
{
    int data;
    Node left, right;

    Node(int item)
    {
        data = item;
        left = right = null;
    }
}

class BinaryTree
{
    Node root1, root2;
      boolean identicalTrees(Node a, Node b)
    {
        Queue<Node> q1 = new LinkedList<Node>();
        Queue<Node> q2 = new LinkedList<Node>();
        if (a == null && b == null)
            return true;

         if (a != null && b != null)
         {
             q1.add(a);
             q2.add(b);

             while(!q1.isEmpty() && ! q2.isEmpty()){
                 Node n1 = q1.peek();
                 Node n2 = q2.peek();

                 if(n1.data != n2.data)
                     return false;

                 q1.remove();
                 q2.remove();

                 if(n1.left!=null && n2.left!=null){
                     q1.add(n1.left);
			         q2.add(n2.left);
                 }
                 else //if (n1.left==null || n2.left==null)
			        return false;

			     if(n1.right!=null && n2.right!=null){
                     q1.add(n1.right);
			         q2.add(n2.right);
                 }
                 else //if (n1.right==null || n2.right==null)
			        return false;
             }
        }
        return true;
     }

public static void main(String[] args)
    {
        BinaryTree tree = new BinaryTree();

        tree.root1 = new Node(1);
        tree.root1.left = new Node(2);
        tree.root1.right = new Node(3);
        tree.root1.left.left = new Node(4);
        tree.root1.left.right = new Node(5);

        tree.root2 = new Node(1);
        tree.root2.left = new Node(2);
        tree.root2.right = new Node(3);
        tree.root2.left.left = new Node(4);
        tree.root2.left.right = new Node(5);

        if (tree.identicalTrees(tree.root1, tree.root2))
            System.out.println("Both trees are identical");
        else
            System.out.println("Trees are not identical");

    }
}