Check If the Two Binary Search Trees are Identical or Not

Rhythm Jain
Last Updated: May 13, 2022

Introduction

Problems on Trees and their applications are commonly asked in programming interviews. Trees are one of the most important topics for preparing for programming interviews of big companies.

That’s why today we are back with an important question based on Binary Trees.

Problem Statement

Given the two binary search trees. If the two Binary Search Trees are identical, print 1; otherwise, print 0. If two trees are architecturally identical and their nodes contain the same values, they are identical.

Example:

Assume we have the following tree as input:

Tree 1

                    5

                  /  \

                3    6

               / \      \

             2   4      8
 

Tree 2

                   5

                  /  \

               3    6

              / \      \

            2   4      8

Output:

1

Explanation:

Since both trees are identical, we return 1.

Approach

To determine whether two trees are the same, we must traverse both trees at the same time and compare the data and children of the trees.

Algorithm:

  • If tree1==null and tree2==null return 1.
  • Else If tree1!=null and tree2!=null,
    • Verify the root node data (tree1->data == tree2->data).
    • Now check for left subtrees - Call sameTree(tree1->left subtree, tree2->left subtree) recursively .
    • Now check for right subtrees - Call sameTree(tree1->right subtree, tree2->right subtree) recursively .
    • If the left and right recursive calls both return 1 then return 1 else return 0.
  • Otherwise, return 0 (one is empty and the other is not).

Code in C++

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
    public:
	int data;
	TreeNode* left;
	TreeNode* right;
	
	TreeNode (int x){
	    data=x;
	    left=NULL;
	    right=NULL;
	}
};

//Function to check Identical Trees
int isIdentical(TreeNode* root1, TreeNode* root2)
{
	// if both the trees are empty return 1
	if (root1 == NULL && root2 == NULL)
		return 1;
	// if only one tree is empty return 0
	else if (root1 != NULL && root2 == NULL)
		return 0;
	else if (root1 == NULL && root2 != NULL)
		return 0;
	else { 
	    // Check for root value of both trees 
		// Check for left subtree and right subtree recursively		
if (root1->data == root2->data && isIdentical(root1->left, root2->left)
			&& isIdentical(root1->right, root2->right))
			return 1;
		else
			return 0;
	}
}

int main()
{
	/*
    Constructed binary tree is:
                   5
                  /  \
               3    6
             / \      \
          2   4      8

     */
    TreeNode* root1 = new TreeNode(5);
    root1->left = new TreeNode(3);
    root1->right = new TreeNode(6);
    root1->left->left = new TreeNode(2);
    root1->left->right = new TreeNode(4);
    root1->right->right = new TreeNode(8);
    
    TreeNode* root2 = new TreeNode(5);
    root2->left = new TreeNode(3);
    root2->right = new TreeNode(6);
    root2->left->left = new TreeNode(2);
    root2->left->right = new TreeNode(4);
    root2->right->right = new TreeNode(8);

	cout <<isIdentical(root1, root2);

	return 0;
}


Output

1

Complexity Analysis

Time Complexity: O(N)

Where N is the number of nodes in the tree.Because we are traversing the whole tree while calling recursively for both left and right subtree. So, we need to visit each node in the tree.

Space Complexity: O(N) 

Since we are recursively calling for left and right subtree, this takes O(N) stack memory for recursion.

Frequently Asked Questions

  1. What is a Binary Tree?
    A binary tree is a non-linear data structure of the tree type, with a maximum of two offspring for each parent. Every node in a binary tree has a left and right reference along with the data element. The root node is at the top of a tree's hierarchy.
     
  2. What is a leaf node?
    Any node in a Binary Tree that has zero children, or in other words, both left and right children are null, is called Leaf Node.
     
  3. What is the height of a complete binary tree with total N nodes?
    For a complete binary tree, the height is ceil(Log(N+1)-1) which is approximately logN. That is why most of the binary tree operations are O(Log N) in nature.

Key Takeaways

A tree is a collection of nodes linked together by edges. These 'trees' constitute a tree-like data structure, with the 'root' node leading to 'parent' nodes, which lead to 'children' nodes.

If you want to master Binary Search Trees, have a look at Binary Search Tree.

If you wish to practice more Tree related problems, you can visit TOP TREES INTERVIEW QUESTIONS.

Happy Coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think