package tree; /* Given two binary trees, write a function to check if they are equal or not. Two binary trees are considered equal if they are structurally identical and the nodes have the same value. Note: Below trees are not identical. Data in all the below trees are same but are structurally different. B C C A / \ / \ / \ \ A D B D A D B / / \ \ C A B C \ D Identical Trees example below, 50 50 / \ / \ / \ / \ 20 80 20 80 / \ / \ / \ / \ 10 30 70 100 10 30 70 100 */ public class CheckTwoTreesAreIdentical { private Node rootNode1; private Node rootNode2; public static void main(String[] args) { new CheckTwoTreesAreIdentical(); } public CheckTwoTreesAreIdentical() { rootNode1 = addNode(rootNode1, 100); rootNode1 = addNode(rootNode1, 30); rootNode1 = addNode(rootNode1, 20); rootNode1 = addNode(rootNode1, 40); rootNode1 = addNode(rootNode1, 200); rootNode2 = addNode(rootNode2, 100); rootNode2 = addNode(rootNode2, 60); rootNode2 = addNode(rootNode2, 20); rootNode2 = addNode(rootNode2, 40); rootNode2 = addNode(rootNode2, 200); System.out.println("Result :"+checkTreeAreIdentical(rootNode1, rootNode2)); } private boolean checkTreeAreIdentical(Node tree1, Node tree2){ if(tree1==null && tree2==null){ //OR if(tree1 == tree2) return true; } if(tree1==null || tree2==null){ return false; } //Data check, Left Tree check and Right Tree check can be done in same line, //but for simplicity I have separated it. if(tree1.getData()!=tree2.getData()){ return false; } boolean isLeftSame = checkTreeAreIdentical(tree1.getLeft(), tree2.getLeft()); boolean isRightSame = checkTreeAreIdentical(tree1.getRight(), tree2.getRight()); if(isLeftSame && isRightSame){ return true; }else{ return false; } } private Node addNode(Node rootNode, int i) { if(rootNode==null){ return new Node(i); }else{ if(i > rootNode.getData()){ Node nodeToAdd = addNode(rootNode.getRight(), i); rootNode.setRight(nodeToAdd); }else{ Node nodeToAdd = addNode(rootNode.getLeft(), i); rootNode.setLeft(nodeToAdd); } } return rootNode; } }
Questions on Stack, Queues, Linkedlist, Binary Trees, Sorting, Searching, Graphs etc with solution using Java Language.
Sunday, 28 June 2015
Given two Binary Trees, write a function to check if they are same. OR Check if given Two Binary Trees are Identical.
Labels:
Binary Search Tree,
Binary Tree