Given two binary trees, find if they are structurally identical.

Question: Given two binary trees, find if they are structurally identical.

Input: 2 trees are given. (Root pointers)
Output: TRUE

When we say structurally identical trees, we mean that both the trees have exactly the same number of nodes, arranged in the exactly same way. It is not necessary that the value of each node should also be the same.

Since, we need to traverse each node of the tree and each node has the same property of having a data value, a left child and a right child, we will proceed with the method of recursion.

The algorithm we will follow will be therefore:-

• If both trees are NULL, return true.
• If both trees are not NULL, then compare data and recursively check left and right sub-tree structures.

Here is an implementation of the above algorithm.

#include<stdio.h>
#include<malloc.h>

struct binaryTreeNode{
	int data;
	struct binaryTreeNode * left;
	struct binaryTreeNode * right;
};

// Function that returns 1 if the trees are
// structurally identical
int areStructurallyIdentical(struct binaryTreeNode * root1, struct binaryTreeNode * root2)
{
	// both NULL , return 1
	if(root1 == NULL && root2 == NULL)
	{
		return 1;
	}
	
	// If one of them is different, return 0
	if(root1 == NULL || root2 == NULL)
	{
		return 0;
	}
	
	// if both are non-empty, compare them
	return (areStructurallyIdentical(root1 -> left , root2 -> left) && areStructurallyIdentical(root1 -> right, root2 -> right))
}

Time Complexity:- O(n)
Space Complexity:- O(n) for the recursive stack