Find given two binary trees are identical

Given two binary trees, check if all the nodes in those binary trees are the same.

Recursively if two binary trees (L1, P1, R1) and (L2, P2, R2) are identical only when P1 = P2 and both (L1, L2) and (R1, R2) subtrees are also identical. Below are the pictorial representation of two identical trees.

A complete binary sample which is identical as the other tree.
Original tree
A complete binary sample which is identical as the other tree.
An identical tree to original tree.
// Mathematical definition.
F(P1, P2) = (P1 == P2) && F(L1, L2) && F(R1, R2) // Where P1 & P2 are not NULL.
F(P1, P2) = TRUE // Where P1 & P2 are both NULL.

Based on the above formula, let’s try to write a recursive solution to find two trees identical or not.

// Recursive approach to find
// given tree are identical or not.
bool identicalRec(
	struct Node *root1,
	struct Node *root2)
{
	if(root1 == NULL && root2 == NULL)
		return true;
	if(root1 == NULL || root2 == NULL)
		return false;

	return (root1->data == root2->data) &&
		identicalRec(root1->left, root2->left) &&
		identicalRec(root1->right, root2->right);
}

Complexity: O(n)

Likewise, instead of using a system stack as in the recursive approach, it uses a stack data structure in an iterative approach to solve this problem. In this approach, first of all it pushes root nodes of both the trees. Compares its content and pushes its left and right children if the content of parents is the same.

If contents are not the same, it considered as non-identical trees. The code for this solution is as shown below.

// An iterative approach to find
// given trees are identical or not.
bool identicalItr(
	struct Node *root1,
	struct Node *root2)
{
	if(root1 == NULL && root2 == NULL)
		return true;
	if(root1 == NULL || root2 == NULL)
		return false;

	stack<pair<struct Node*, struct Node*> > stk;
	stk.push(make_pair(root1, root2));

	while(!stk.empty())
	{
		Node *tmp1 = stk.top().first;
		Node *tmp2 = stk.top().second;
		stk.pop();

		if(tmp1->data != tmp2->data)
			return false;

		if(tmp1->left && tmp2->left)
			stk.push(make_pair(tmp1->left, tmp2->left));
		else if(tmp1->left || tmp2->left)
			return false;

		if(tmp1->right && tmp2->right)
			stk.push(make_pair(tmp1->right, tmp2->right));
		else if(tmp1->right || tmp2->right)
			return false;
	}
	return true;
}

Complexity: O(n)

Hence, defined two possible recursive and iterative approaches to solve this identical tree problem. The complete code can be as follows.

// Output
Trees Identical (Recursive): TRUE
Trees Identical (Iterative): TRUE

If you find anything wrong with the algorithm or code, please let the reader know by commenting here below. Cheers!.