CSharp  Java  Python  Swift  GO  WPF  Ruby  Scala  F#  JavaScript  SQL  PHP  Angular  HTML
Q. Program to determine whether two trees are identical.ExplanationIn this program, we need to check whether two trees are identical or not. For two trees to be identical, they have to satisfy two conditions:
Above diagram contains three trees namely A, B, and C. Trees A and B are the identical as they are structurally same and values of all nodes are the same. However, trees A and C are structurally same but not identical as nodes are different in both the trees. Algorithm
SolutionPython#Represent a node of binary tree class Node: def __init__(self,data): #Assign data to the new node, set left and right children to None self.data = data; self.left = None; self.right = None; class IdenticalTrees: def __init__(self): #Represent the root of binary tree self.root = None; #areIdenticalTrees() finds whether two trees are identical or not @staticmethod def areIdenticalTrees(root1, root2): #Checks if both the trees are empty if(root1 == None and root2 == None): return True; #Trees are not identical if root of only one tree is null thus, return false if(root1 == None and root2 == None): return True; #If both trees are not empty, check whether the data of the nodes is equal #Repeat the steps for left subtree and right subtree if(root1 != None and root2 != None): return ((root1.data == root2.data) and (IdenticalTrees.areIdenticalTrees(root1.left, root2.left)) and (IdenticalTrees.areIdenticalTrees(root1.right, root2.right))); return False; #Adding nodes to the first binary tree bt1 = IdenticalTrees(); bt1.root = Node(1); bt1.root.left = Node(2); bt1.root.right = Node(3); bt1.root.left.left = Node(4); bt1.root.right.left = Node(5); bt1.root.right.right = Node(6); #Adding nodes to the second binary tree bt2 = IdenticalTrees(); bt2.root = Node(1); bt2.root.left = Node(2); bt2.root.right = Node(3); bt2.root.left.left = Node(4); bt2.root.right.left = Node(5); bt2.root.right.right = Node(6); #Displays whether both the trees are identical or not if(IdenticalTrees.areIdenticalTrees(bt1.root, bt2.root)): print("Both the binary trees are identical"); else: print("Both the binary trees are not identical"); Output: Both the binary trees are identical C#include <stdio.h> #include <stdlib.h> #include <stdbool.h> //Represent a node of binary tree struct node{ int data; struct node *left; struct node *right; }; //Represent the root node of first binary tree struct node *rootTree1 = NULL; //Represent the root node of second binary tree struct node *rootTree2 = NULL; //createNode() will create a new node struct node* createNode(int data){ //Create a new node struct node *newNode = (struct node*)malloc(sizeof(struct node)); //Assign data to newNode, set left and right children to NULL newNode>data= data; newNode>left = NULL; newNode>right = NULL; return newNode; } //areIdenticalTrees() finds whether two trees are identical or not bool areIdenticalTrees(struct node *root1, struct node *root2) { //Checks if both the trees are empty if(root1 == NULL && root2 == NULL) return true; //Trees are not identical if root of only one tree is null thus, return false if(root1 == NULL && root2 == NULL) return true; //If both trees are not empty, check whether the data of the nodes is equal //Repeat the steps for left subtree and right subtree if(root1 != NULL && root2 != NULL) { return ((root1>data == root2>data) && (areIdenticalTrees(root1>left, root2>left)) && (areIdenticalTrees(root1>right, root2>right))); } return false; } int main() { //Adding nodes to the first binary tree rootTree1 = createNode(1); rootTree1>left = createNode(2); rootTree1>right = createNode(3); rootTree1>left>left = createNode(4); rootTree1>right>left = createNode(5); rootTree1>right>right = createNode(6); //Adding nodes to the second binary tree rootTree2 = createNode(1); rootTree2>left = createNode(2); rootTree2>right = createNode(3); rootTree2>left>left = createNode(4); rootTree2>right>left = createNode(5); rootTree2>right>right = createNode(6); //Displays whether both the trees are identical or not if(areIdenticalTrees(rootTree1, rootTree2)) printf("Both the binary trees are identical"); else printf("Both the binary trees are not identical"); return 0; } Output: Both the binary trees are identical JAVApublic class IdenticalTrees { //Represent the node of the binary tree public static class Node{ int data; Node left; Node right; //Assign data to the new node, set left and right children to null public Node(int data){ this.data = data; this.left = null; this.right = null; } } //Represent the root of the binary tree public Node root; public IdenticalTrees(){ root = null; } //areIdenticalTrees() finds whether two trees are identical or not public static boolean areIdenticalTrees(Node root1, Node root2) { //Checks if both the trees are empty if(root1 == null && root2 == null) return true; //Trees are not identical if root of only one tree is null thus, return false if(root1 == null && root2 == null) return true; //If both trees are not empty, check whether the data of the nodes is equal //Repeat the steps for left subtree and right subtree if(root1 != null && root2 != null) { return ((root1.data == root2.data) && (areIdenticalTrees(root1.left, root2.left)) && (areIdenticalTrees(root1.right, root2.right))); } return false; } public static void main(String[] args) { //Adding nodes to the first binary tree IdenticalTrees bt1 = new IdenticalTrees(); bt1.root = new Node(1); bt1.root.left = new Node(2); bt1.root.right = new Node(3); bt1.root.left.left = new Node(4); bt1.root.right.left = new Node(5); bt1.root.right.right = new Node(6); //Adding nodes to the second binary tree IdenticalTrees bt2 = new IdenticalTrees(); bt2.root = new Node(1); bt2.root.left = new Node(2); bt2.root.right = new Node(3); bt2.root.left.left = new Node(4); bt2.root.right.left = new Node(5); bt2.root.right.right = new Node(6); //Displays whether both the trees are identical or not if(areIdenticalTrees(bt1.root, bt2.root)) System.out.println("Both the binary trees are identical"); else System.out.println("Both the binary trees are not identical"); } } Output: Both the binary trees are identical C#using System; namespace Tree { public class Program { //Represent a node of binary tree public class Node<T>{ public T data; public Node<T> left; public Node<T> right; public Node(T data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } public class IdenticalTrees<T>{ //Represent the root of binary tree public Node<T> root; public IdenticalTrees(){ root = null; } //areIdenticalTrees() finds whether two trees are identical or not public static Boolean areIdenticalTrees(Node<T> root1, Node<T> root2) { //Checks if both the trees are empty if(root1 == null && root2 == null) return true; //Trees are not identical if root of only one tree is null thus, return false if(root1 == null && root2 == null) return true; //If both trees are not empty, check whether the data of the nodes is equal //Repeat the steps for left subtree and right subtree if(root1 != null && root2 != null) { return ((root1.data.Equals(root2.data)) && (areIdenticalTrees(root1.left, root2.left)) && (areIdenticalTrees(root1.right, root2.right))); } return false; } } public static void Main() { //Adding nodes to the first binary tree IdenticalTrees<int> bt1 = new IdenticalTrees<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); //Adding nodes to the second binary tree IdenticalTrees<int> bt2 = new IdenticalTrees<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); //Displays whether both the trees are identical or not if(IdenticalTrees<int>.areIdenticalTrees(bt1.root, bt2.root)) Console.WriteLine("Both the binary trees are identical"); else Console.WriteLine("Both the binary trees are not identical"); } } } Output: Both the binary trees are identical PHP<!DOCTYPE html> <html> <body> <?php //Represent a node of binary tree class Node{ public $data; public $left; public $right; function __construct($data){ //Assign data to the new node, set left and right children to NULL $this>data = $data; $this>left = NULL; $this>right = NULL; } } class IdenticalTrees{ //Represent the root of binary tree public $root; function __construct(){ $this>root = NULL; } //areIdenticalTrees() finds whether two trees are identical or not static function areIdenticalTrees($root1, $root2) { //Checks if both the trees are empty if($root1 == NULL && $root2 == NULL) return true; //Trees are not identical if root of only one tree is null thus, return false if($root1 == NULL && $root2 == NULL) return true; //If both trees are not empty, check whether the data of the nodes is equal //Repeat the steps for left subtree and right subtree if($root1 != NULL && $root2 != NULL) { return (($root1>data == $root2>data) && (IdenticalTrees::areIdenticalTrees($root1>left, $root2>left)) && (IdenticalTrees::areIdenticalTrees($root1>right, $root2>right))); } return false; } } //Adding nodes to the first binary tree $bt1 = new IdenticalTrees(); $bt1>root = new Node(1); $bt1>root>left = new Node(2); $bt1>root>right = new Node(3); $bt1>root>left>left = new Node(4); $bt1>root>right>left = new Node(5); $bt1>root>right>right = new Node(6); //Adding nodes to the second binary tree $bt2 = new IdenticalTrees(); $bt2>root = new Node(1); $bt2>root>left = new Node(2); $bt2>root>right = new Node(3); $bt2>root>left>left = new Node(4); $bt2>root>right>left = new Node(5); $bt2>root>right>right = new Node(6); //Displays whether both the trees are identical or not if(IdenticalTrees::areIdenticalTrees($bt1>root, $bt2>root)) print("Both the binary trees are identical"); else print("Both the binary trees are not identical"); ?> </body> </html> Output: Both the binary trees are identical
Next TopicPrograms List
