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



Thanks for feedback.



Read More....
Check if a binary tree is a min heap
Check if a binary tree is symmetric or mirror of itself
Check if a binary tree is symmetric or mirror of itself - iterative
Create a mirror of binary tree - Iterative approach
Create a mirror of binary tree - Recursive approach
Find the height of binary tree - Iterative approach