Identical Binary Trees Editorial

Practice Problem Link: Identical Binary Trees

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

If two binary trees share the exact same structure and have the same node values, they are considered identical.

Given references to the root nodes of two binary trees, find out if the trees are identical or not.

Approach (BFS)

The idea is to do a level order traversal for both the trees simultaneously and compare the corresponding elements of both the trees.

Analysis

• Time Complexity: O(n + m)
• Auxiliary Space Complexity: O(n + m)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/

bool areIdenticalTrees(Node* root1, Node* root2) {
    queue<Node*> tree1, tree2;
	tree1.push(root1);
	tree2.push(root2);
	while (!tree1.empty() && !tree2.empty()) {
		Node* currentNode1 = tree1.front();
		tree1.pop();
		Node* currentNode2 = tree2.front();
		tree2.pop();
		if (currentNode1->data != currentNode2->data) {
			return false;
		}
		if (currentNode1->left != NULL) {
			tree1.push(currentNode1->left);
		}
		if (currentNode1->right != NULL) {
			tree1.push(currentNode1->right);
		}
		if (currentNode2->left != NULL) {
			tree2.push(currentNode2->left);
		}
		if (currentNode2->right != NULL) {
			tree2.push(currentNode2->right);
		}
	}
	if (!tree1.empty() || !tree2.empty()) {
		return false;
	}
	return true;
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
	
	boolean areIdenticalTrees(Node root1, Node root2) {
	    Queue<Node> tree1 = new LinkedList<Node> ();
	    Queue<Node> tree2 = new LinkedList<Node> ();
		tree1.add(root1);
		tree2.add(root2);
		while (!tree1.isEmpty() && !tree2.isEmpty()) {
			Node currentNode1 = tree1.peek();
			tree1.poll();
			Node currentNode2 = tree2.peek();
			tree2.poll();
			if (currentNode1.data != currentNode2.data) {
				return false;
			}
			if (currentNode1.left != null) {
				tree1.add(currentNode1.left);
			}
			if (currentNode1.right != null) {
				tree1.add(currentNode1.right);
			}
			if (currentNode2.left != null) {
				tree2.add(currentNode2.left);
			}
			if (currentNode2.right != null) {
				tree2.add(currentNode2.right);
			}
		}
		if (!tree1.isEmpty() || !tree2.isEmpty()) {
			return false;
		}
		return true;
	}
}

Approach (DFS)

The idea is to traverse both the trees recursively and check if every node and its children subtrees for both the trees are equal or not.

Analysis

• Time Complexity: O(n + m)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/

bool areIdenticalTrees(Node* root1, Node* root2) {
    if(root1 == NULL && root2 == NULL) {
		return true;
	}
	if(root1 == NULL || root2 == NULL) {
		return false;
	}
	if(root1->data != root2->data) {
		return false;
	}
	if(areIdenticalTrees(root1->left, root2->left) == false || areIdenticalTrees(root1->right, root2->right) == false) {
		return false;
	}
	return true;
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
	
	boolean areIdenticalTrees(Node root1, Node root2) {
	    if(root1 == null && root2 == null) {
			return true;
		}
		if(root1 == null || root2 == null) {
			return false;
		}
		if(root1.data != root2.data) {
			return false;
		}
		if(areIdenticalTrees(root1.left, root2.left) == false || areIdenticalTrees(root1.right, root2.right) == false) {
			return false;
		}
		return true;
	}
}