Question

Write an algorithm to determine if two binary trees are identical when the ordering of the subtrees 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?

Answer 1

/* To identify if two trees are identical, we need to traverse both trees simultaneously,
and while traversing we need to compare data and children of the trees. */
/*
Algorithm:

IdenticalTree(tree1, tree2)
1. If both trees are empty then return 1.
2. Else If both trees are non -empty
(a) Check data of the root nodes (tree1->data == tree2->data)
(b) Check left subtrees recursively i.e., call IdenticalTree(
tree1->left_subtree, tree2->left_subtree)
(c) Check right subtrees recursively i.e., call IdenticalTree(
tree1->right_subtree, tree2->right_subtree)
(d) If a,b and c are true then return 1.
3 Else return 0 (one is empty and other is not)

*/

// C++ Implimentation of above algorithm
  
#include <iostream>
using namespace std;
  
// BST node
struct Node {
int data;
struct Node* left;
struct Node* right;
};
  
// Utility function to create a new Node
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;
}
  
// Function to perform inorder traversal
void inorder(Node* root)
{
if (root == NULL)
return;
  
inorder(root->left);
  
cout << root->data << " ";
  
inorder(root->right);
}
  
// Function to check if two If two binary trees
// are identical when the ordering of subtrees for the nodes is ignored.
int isIdentical(Node* root1, Node* root2)
{
// Check if both the trees are empty
if (root1 == NULL && root2 == NULL)
return 1;
// If any one of the tree is non-empty
// and other is empty, return false
else if (root1 != NULL && root2 == NULL)
return 0;
else if (root1 == NULL && root2 != NULL)
return 0;
else { // Check if current data of both trees equal
// and recursively check for left and right subtrees
if (root1->data == root2->data && ((isIdentical(root1->left, root2->left)
&& isIdentical(root1->right, root2->right) )||(isIdentical(root1->left, root2->right)&& isIdentical(root1->right, root2->left))))
return 1;
else
return 0;
}
}
  
// Driver code
int main()
{
struct Node* root1 = newNode(5);
struct Node* root2 = newNode(5);
root1->left = newNode(3);
root1->right = newNode(8);
root1->left->left = newNode(2);
root1->left->right = newNode(4);
  
root2->left = newNode(8);
root2->right = newNode(3);
root2->right->left = newNode(4);
root2->right->right = newNode(2);
  
if (isIdentical(root1, root2))
cout << "Both Binary Trees are identical";
else
cout << "Binary Trees are not identical";
  
return 0;
}

/* Complexity of the identicalTree() will be according to
the tree with lesser number of nodes. Let number of nodes in
two trees be m and n then the complexity of identicalTree() is O(m) where m < n.
*/