Write a C++ function that returns True if two trees are structurally identical.(
ID: 3765028 • Letter: W
Question
Write a C++ function that returns True if two trees are structurally identical.(they are made of nodes with the same values arranged in the same way.) The function takes two arguments: treenode of tree1 and treenode of tree2. It should return True if the trees are identical. Otherwise, return False.
bool sameTree(TreeNode *node1, TreeNode *node2);
For example:
Test Result Input:Tree 1
11
/
7 14
/
2 8
/
1 5
/
4
Tree 2
11
/
7 14
/
2 8
/
1 5
/
4
Explanation / Answer
nclude <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* Given two trees, return true if they are
structurally identical */
int identicalTrees(struct node* a, struct node* b)
{
/*1. both empty */
if (a==NULL && b==NULL)
return 1;
/* 2. both non-empty -> compare them */
if (a!=NULL && b!=NULL)
{
return
(
a->data == b->data &&
identicalTrees(a->left, b->left) &&
identicalTrees(a->right, b->right)
);
}
/* 3. one empty, one not -> false */
return 0;
}
/* Driver program to test identicalTrees function*/
int main()
{
struct node *root1 = newNode(1);
struct node *root2 = newNode(1);
root1->left = newNode(2);
root1->right = newNode(3);
root1->left->left = newNode(4);
root1->left->right = newNode(5);
root2->left = newNode(2);
root2->right = newNode(3);
root2->left->left = newNode(4);
root2->left->right = newNode(5);
if(identicalTrees(root1, root2))
printf("Both tree are identical.");
else
printf("Trees are not identical.");
getchar();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.