Site icon Study Algorithms

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)
tree_structure_identical_question 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:-

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

Exit mobile version