Binary Tree: Program to check if two binary tree are identical

Write a program to check if two binary trees are identical

To check if two binary trees are identical or not, we have to check their all three (inorder, preorder and postorder) traversals
There can be cases where inorder & preorder traversals are same between two trees but the trees are different.
So we are required to test for all three traversals to make sure the two trees are identical.

Algorithm

1. Create two arraylist say result1 and result2 for storing traversal results
2. Call inorder function for both binary trees and stored result in respective arraylist result1 and result2
3. If result1 is not equal to result2, return false
4. Clear result1 and result2
5. Call preorder function for both binary trees and stored result in respective arraylist result1 and result2
6. If result1 is not equal to result2, return false
7. Clear result1 and result2
8. Call postorder function for both binary trees and stored result in respective arraylist result1 and result2
9. If result1 is not equal to result2, return false
10. If all traversals are match then return true

Diagram

Complexity

Time Complexity : O(n) , where n is the number of nodes in binary tree
Space Complexity : O(1)

Java Code

import java.util.*;

    class BinaryTreeIdentical{
    
        static class Node {
     
            int data;
            Node left, right;
     
            Node(int element) {
                data = element;
                left = right = null;
            }
        }
     
        Node root;
     
        public static Node constructBinaryTree(int[] arr, int i) {
            Node root = null;
            if (i < arr.length) {
                root = new Node(arr[i]);
                root.left = constructBinaryTree(arr, 2 * i + 1);
                root.right = constructBinaryTree(arr, 2 * i + 2);
            }
            return root;
        }
     
     
        static void inOrder(Node root, ArrayList output) {
            if (root == null)
                return;
            
            inOrder(root.left, output);
            output.add(root.data);
            inOrder(root.right, output);
        }
     
        static void preOrder(Node root, ArrayList output) {
            if (root == null)
                return;
    
            output.add(root.data);
            preOrder(root.left, output);
            preOrder(root.right, output);
        }
     
        static void postOrder(Node root, ArrayList output) {
            if (root == null)
                return;
    
            postOrder(root.left, output);
            postOrder(root.right, output);
            output.add(root.data);
        }
     
        static boolean isTreesIdentical(Node root1, Node root2) {
            ArrayList result1 = new ArrayList();
            ArrayList result2 = new ArrayList();
     
            inOrder(root1, result1);
            inOrder(root2, result2);
            if (!result1.equals(result2))
                return false;
     
            result1.clear();
            result2.clear();
     
            preOrder(root1, result1);
            preOrder(root2, result2);
            if (!result1.equals(result2))
                return false;
     
            result1.clear();
            result2.clear();
     
            postOrder(root1, result1);
            postOrder(root2, result2);
            if (!result1.equals(result2))
                return false;
     
            return true;
        }
     
        public static void main(String args[]) {
            BinaryTreeIdentical tt1 = new BinaryTreeIdentical();
            BinaryTreeIdentical tt2 = new BinaryTreeIdentical();
            int[] bstElements1 = new int[] { 50, 20, 30, 10, 200, 70, 90 };
            tt1.root = tt1.constructBinaryTree(bstElements1, 0);
            int[] bstElements2 = new int[] { 60, 20, 50, 80, 40, 56, 30, 100, 75 };
            tt2.root = tt2.constructBinaryTree(bstElements2, 0);
            if (isTreesIdentical(tt1.root, tt2.root)) {
                System.out.println("Given Binary Tree are identical ");
            } else {
                System.out.println("Given Binary Tree are not identical ");
            }
        }
  }  

Output

Given Binary Tree are not identical