Identical binary trees

Given two binary trees, check if two trees are identical binary trees? First question arises : when do you call two binary trees are identical? If root of two trees is equal and their left and right subtrees are also identical, then two trees are called as identical binary trees. For example, two trees below are identical.

identical binary trees

whereas these two trees are not identical as node  6 and 8 differ as well as node 14 and 16.

identical binary trees

Identical binary trees : Thoughts

Solution to the problem lies in the definition of identical tree itself. We check if roots are equal, if there are not, there is no point continue down the tree, just return that trees are not identical.
If roots are equal, we have to check is subtrees are equal. To do, so take left subtrees of both original trees and validate if left subtrees are identical too. If not, return negative response. If yes, check if right subtrees are identical too.

Did you notice two things? First, that solution to original problem depends on solution of subtrees and at each node problem reduces itself to smaller subproblem.
Second,  processing order is preorder, we process roots of two trees, then left subtrees and at last right subtree. As Mirror binary search tree and Delete binary search tree are solved using postorder traversal, this problem can be solved using preorder traversal with special processing at root node.

We can also solve it by postorder traversal too, in that case, we will be unnecessary scanning subtrees even when roots themselves are not equal.

Identical binary trees : example

Let’s take an example and see how it works. Start with root nodes, both roots are equal, move down to left subtree.

Left node in both subtrees is node(5), which is again equal. Go down the left subtree.

Again, left nodes in both subtrees is node(1), move down the left subtrees of both.

As per definition, two empty binary trees are identical. So when we move down the left child of nodes, they are null, hence identical and we return true to parent node(1). Same is true for right child.

We already know that at node(1), left and right subtree are identical, as well as node values are equal, we return true to parent node(5).

Left subtrees of node(5) are identical, move to right subtree to node(6). Similar to node(1), it also return true to parent node.

At node(5), left and right subtrees are identical, and also node values are equal, we return true to node(10).

is identical bst

Left subtrees are identical, now go to right subtree of node(10) in both trees.

is identical binary tree

Node(14) are equal in both trees, so check left subtrees of node(14) of both trees are identical. Both left subtree and right subtree of node(14) identical, same as node(1) and node(6) in left subtree, so they return true to parent node(14).

identical binary search tree

Now, at node(14), left and right subtrees are identical, so return true up to parent node(10).

Now, at  root node of both trees, there left subtrees and right subtrees are identical, so we return true for question if these two trees are identical or not.

Can you draw non identical binary trees and come up with flow and determine when they will be called out to be non-identical?

Identical binary trees : Implementation

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
    int value;
    struct node *left;
    struct node *right;
};
typedef struct node Node;

#define true 1
#define false 0

void inoderTraversal(Node * root){
    if(!root) return;
    
    inoderTraversal(root->left);
    printf("%d ", root->value);
    inoderTraversal(root->right);
}

Node *createNode(int value){
    Node * newNode =  (Node *)malloc(sizeof(Node));
    
    newNode->value = value;
    newNode->right= NULL;
    newNode->left = NULL;
    
    return newNode;
}

Node *addNode(Node *node, int value){
    if(!node) return createNode(value);
    
    if (node->value > value)
        node->left = addNode(node->left, value);
    else
        node->right = addNode(node->right, value);
    
    return node;
}

int isIdenticalBST( Node * firstTree, Node *secondTree){
    if( ! (firstTree || secondTree ) ) //both of them are empty
        return true;
    
    if( !( firstTree && secondTree ) ) // one of them is empty
        return false;
    
    return ( firstTree->value == secondTree->value )
        && isIdenticalBST( firstTree->left, secondTree->left )
        && isIdenticalBST( firstTree->right, secondTree->right );
}

/* Driver program for the function written above */
int main(){
    Node *firstRoot = NULL;
	
    //Creating a binary tree
    firstRoot = addNode(firstRoot, 30);
    firstRoot = addNode(firstRoot, 20);
    firstRoot = addNode(firstRoot, 15);
    firstRoot = addNode(firstRoot, 25);
    firstRoot = addNode(firstRoot, 40);
    firstRoot = addNode(firstRoot, 38);
    firstRoot = addNode(firstRoot, 45);
    
    printf("Inorder traversal of tree is : ");
    inoderTraversal(firstRoot);
	
    printf("\n");
    
    Node *secondRoot = NULL;
    
    //Creating a binary tree
    secondRoot = addNode(secondRoot, 30);
    secondRoot = addNode(secondRoot, 20);
    secondRoot = addNode(secondRoot, 15);
    secondRoot = addNode(secondRoot, 25);
    secondRoot = addNode(secondRoot, 40);
    secondRoot = addNode(secondRoot, 38);
    secondRoot = addNode(secondRoot, 45);
    
    printf("Inorder traversal of tree is : ");
    inoderTraversal(secondRoot);
    printf("\n");
    
    printf( "Two trees are identical : %s" , 
           isIdenticalBST( firstRoot, secondRoot ) ? "True" :"false");

    return 0;
}

Complexity to find if two trees are identical binary trees is O(n) where n is number of trees in smaller tree.

Please share if there is something wrong or missing. If you are willing to contribute and share your knowledge with thousands of learners across the world, please reach out to us communications@algorithmsandme.com