In this post, We will learn about How do you find if two given binary trees are the same or identical?
Here We have to write a method in Java, which is going to accept two binary trees and return true if they are the same, otherwise, return false.
Algorithm:
- If both trees are NULL then we return true
- if both trees are NOT NULL then we recursively check left and right subtree structures.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
/** * Function to check whether two trees are * Structurally identical or not? * @param rootNode1 root Node of first tree * @param rootNode2 root Node of Second tree * @return true if both the trees are Structurally identical */ public boolean checkStructurallySameTrees(Node<Integer> rootNode1, Node<Integer> rootNode2) { //If both trees are null then return true if(rootNode1 == null && rootNode2 == null) return true; //If any one tree is null then return false if(rootNode1 == null || rootNode2 == null) return false; /*If both trees are NOT NULL then we check recursively left and right subtree structures*/ return checkStructurallySameTrees(rootNode1.left, rootNode2.right) && checkStructurallySameTrees(rootNode1.right, rootNode2.left); } |
Time Complexity : O(n) , Space Complexity : O(n) for recusive Stack
Below is the Complete Source code:
BinaryTree.java
|
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 |
package com.kkjavatutorials.tree; public class BinaryTree<E extends Comparable<? super E>> { /** * This internal class represents Node in Binary tree * @author KK JavaTutorials */ public static class Node<T> { //Data hold by Binary Tree Node public T data; //Left pointer/reference public Node<T> left; //Right pointer/reference public Node<T> right; public Node(T data) { this.data = data; } } /** * Recursive method for Binary Tree preOrder Processing * @param root Node */ public void preOrder(Node<E> root) { if(root != null) { System.out.print(root.data+" "); preOrder(root.left); preOrder(root.right); } } /** * Function to check whether two trees are * Structurally identical or not? * @param rootNode1 root Node of first tree * @param rootNode2 root Node of Second tree * @return true if both the trees are Structurally identical */ public boolean checkStructurallySameTrees(Node<Integer> rootNode1, Node<Integer> rootNode2) { //If both trees are null then return true if(rootNode1 == null && rootNode2 == null) return true; //If any one tree is null then return false if(rootNode1 == null || rootNode2 == null) return false; /*If both trees are NOT NULL then we check recursively left and right subtree structures*/ return checkStructurallySameTrees(rootNode1.left, rootNode2.right) && checkStructurallySameTrees(rootNode1.right, rootNode2.left); } } |
ClientTest.java
|
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 |
package com.kkjavatutorials.client; import com.kkjavatutorials.tree.BinaryTree; import com.kkjavatutorials.tree.BinaryTree.Node; /** * Client Program to check two Trees are * Structurally identical or Not ? * @author KK JavaTutorials */ public class ClientTest { public static void main(String[] args) { //Create an Instance of BinaryTree BinaryTree<Integer> binaryTree = new BinaryTree<>(); //Root Node1 Node<Integer> rootNode1 = new Node<Integer>(1); Node<Integer> secondNode = new Node<Integer>(2); Node<Integer> thirdNode = new Node<Integer>(3); Node<Integer> fourthNode = new Node<Integer>(4); Node<Integer> fifthNode = new Node<Integer>(5); Node<Integer> sixthNode = new Node<Integer>(6); Node<Integer> seventhNode = new Node<Integer>(7); //Setting Left and right nodes of rootNode1 rootNode1.left = secondNode; rootNode1.right = thirdNode; rootNode1.left.left = fourthNode; rootNode1.left.right = fifthNode; rootNode1.right.left = sixthNode; rootNode1.right.right = seventhNode; //Root Node1 Node<Integer> rootNode2 = new Node<Integer>(1); // Setting Left and right nodes of rootNode2 rootNode2.left = secondNode; rootNode2.right = thirdNode; rootNode2.left.left = fourthNode; rootNode2.left.right = fifthNode; rootNode2.right.left = sixthNode; rootNode2.right.right = seventhNode; //rootNode2.right.right.left = new Node<Integer>(10); //Call for preOrder processing System.out.println("Binary Tree PreOrder Processing output of both Trees...."); binaryTree.preOrder(rootNode1); System.out.println(); binaryTree.preOrder(rootNode2); System.out.println(); System.out.println("-----------------------------------"); boolean isBothTreesIdentical = binaryTree.checkStructurallySameTrees(rootNode1,rootNode2); if(isBothTreesIdentical) { System.out.println("Both Trees are Structurally identical"); }else { System.out.println("Both Trees are Structurally not identical"); } } } |
The output of This Program:
Binary Tree PreOrder Processing output of both Trees….
1 2 4 5 3 6 7
1 2 4 5 3 6 7
———————————–
Both Trees are Structurally identical
You May Also Like:
Introduction to Tree Data Structure
Introduction to Binary Tree
Structure of Binary Trees
Operations and use of Binary Trees
Insert operation in a binary search tree
Delete operation in a binary search tree
Search operation in a binary search tree
Binary Tree Traversals
PreOrder traversal of binary tree implementation in Java
InOrder traversal of binary tree implementation in Java
PostOrder traversal of binary tree implementation in Java
Find the node with minimum and maximum values in a Binary Search Tree
Find a mirror image of a binary tree
Difference between binary and binary search trees
That’s all about How do you find if two given binary trees are the same or identical?
If you have any feedback or suggestion please feel free to drop in below comment box.