Thread: Find two given trees are same

You have two binary trees, how will you find that both trees are same. (structurally equal)

Code:

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

typedef struct binTree* Tree;

/*
Given two trees, return true if they are
structurally identical.
*/

int sameTree(Tree T1, Tree T2) {
	
	// 1. both empty -> true
	if (T1==NULL && T2==NULL) 
		return(true);

	// 2. both non-empty -> compare them
	else if (T1!=NULL && T2!=NULL) {
		return(T1->data == T2->data && sameTree(T1->left, T2->left) && sameTree(T1->right, T2->right) );
	}

	// 3. one empty, one not -> false
	else 
		return(false);
}