Check if two binary trees are identical

Algorithm/Insights

Solution uses recursion to find out if the trees are identical.
1. If root of both trees are null, then they are same. Return true.
2. If roots of both the trees are not null, check if the data in the two nodes is same and recursively check if left and right subtrees are identical.
3. If the roots of only one of the trees is null, then the trees are not identical, so return false.
Please checkout code snippet and algorithm visualization section for understanding the algoithm.

Code Snippet

			
package com.ideserve.questions.saurabh;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Given two trees, find if if they are identical. Two trees are said to be identical if they are structurally same and have same data in all nodes.
 *
 * @author Saurabh
 */
public class IdenticalTree {

	public static boolean areIdenticalTrees(TreeNode root1, TreeNode root2) {
		// If both the tree nodes are null, then both are identical
		if(root1 == null && root2 == null) {
			return true;
		}
		if(root1 != null && root2 != null) {
			// Check if the 2 nodes have same data and recursively check if left and right subtrees are identical
			return ((root1.getData() == root2.getData()) &&
					(areIdenticalTrees(root1.getLeft(), root2.getLeft()) &&
					(areIdenticalTrees(root1.getRight(), root2.getRight()))));
					
					
		}
		// If either of root1 or root2 is null but not both, then the trees are not identical
		return false;
	}
	
	/*
	 * Create a sample tree
	 * 				1
	 * 		2				3
	 * 4		5		6		7
	 * 
	 */
	public static TreeNode createSampleTree() {
		return new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)));		
	}
	
	public static void main(String[] args) {
		TreeNode t1 = IdenticalTree.createSampleTree();
		TreeNode t2 = IdenticalTree.createSampleTree();
		System.out.println(IdenticalTree.areIdenticalTrees(t1, t2) ? "The trees are identical" : " The trees are not identical");
	}
}

class TreeNode {
	
	private int data;
	private TreeNode left;
	private TreeNode right;
	
	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	public TreeNode getLeft() {
		return left;
	}

	public void setLeft(TreeNode left) {
		this.left = left;
	}

	public TreeNode getRight() {
		return right;
	}

	public void setRight(TreeNode right) {
		this.right = right;
	}

	public TreeNode(int data) {
		this.data = data;
	}
	
	public TreeNode(int data, TreeNode left, TreeNode right) {
		this.data = data;
		this.left = left;
		this.right = right;
	}	
}
		

Order of the Algorithm

Time Complexity is O(n) since all nodes of both trees are visited in the worst case.
Space Complexity is O(1)