[6 points] Write a C++ function to determine if two binary trees are identical w
ID: 3724454 • Letter: #
Question
[6 points] Write a C++ function to determine if two binary trees are identical when the ordering of the sub-trees for a node is ignored. For example, if a tree has root node with value R, left child with value A and right child with value B, this would be considered identical to another tree with root node value R, left child value B, and right child value A. Make the algorithm as efficient as you can. Analyze your algorithm's running time. How much harder would it be to make this algorithm work on a general tree?Explanation / Answer
==========================Below code is defining the node of a binary tree==========
#include <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;
};
======== below code is the desired function using recursion which leads to less code and high performance====
/* Given two trees, return true if they are identical in structure and data */
int identicalTrees(struct node* rootA, struct node* rootB)
{
/* case 1. both empty */
if (rootA==NULL && rootB==NULL)
return 1;
/* case 2. both non-empty -> compare them */
if (rootA!=NULL && rootB!=NULL)
{
return
(
rootA->data == rootB->data &&
identicalTrees(rootA->left, rootB->left) &&
identicalTrees(rootA->right, rootB->right)
);
}
/* case 3. one empty, one not -> false */
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.