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