## Tuesday, 10 January 2017

### Check two trees are identical or not

Problem:
Given two binary trees, write a function to check if they are equal or not.

Solution:
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Algorithm:
isTreesIdenticalRec(Node root1, Node root2) :
1. Termination Condition: If both trees are empty then return true.
2. else if both trees are non-empty
(a) Check data of the root nodes (root1->data ==  root2->data)
(b) Check left subtrees recursively
call isTreesIdenticalRec(root1->left, root2->left)
(c) Check right subtrees recursively
call isTreesIdenticalRec(root1->right, root2->right)
(d) If a,b and c are true then return true.
3. else return false(=one is empty and another is not).

package crack.coding.interview;
/**
* Class to check whether two binary trees are identical.
* @author rajesh.dixit
*/
class IdenBinaryTree {

/**
* @author rajesh.dixit
* Node of the Tree.
*/
private static class Node {
int data;
Node left, right;

Node(int item) {
data = item;
left = right = null;
}
}

Node root1, root2;

/**
* To check whether Trees are Identical or not.
* @param root1
* @param root2
* @return true/false
*/
private static boolean isTreesIdenticalRec(Node root1, Node root2) {

if(root1==null && root2==null) {
return true;
} else if(root1!=null && root2!=null) {
return (root1.data == root2.data
&& isTreesIdenticalRec(root1.left, root2.left)
&& isTreesIdenticalRec(root1.right, root2.right));
} else {
return false;
}
}

/**
* Main method: Program start point.
* @param args
*/
public static void main(String[] args) {

IdenBinaryTree tree1 = new IdenBinaryTree();
tree1.root1 = new Node(1);
tree1.root1.left = new Node(2);
tree1.root1.right = new Node(3);
tree1.root1.left.left = new Node(4);
tree1.root1.left.right = new Node(5);

IdenBinaryTree tree2 = new IdenBinaryTree();
tree2.root2 = new Node(1);
tree2.root2.left = new Node(2);
tree2.root2.right = new Node(3);
tree2.root2.left.left = new Node(4);
tree2.root2.left.right = new Node(5);

if (isTreesIdenticalRec(tree1.root1, tree2.root2)) {
System.out.println("Trees are identical");
} else {
System.out.println("Trees are not identical");
}
}
}