Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

Introduction

Binary Search Trees (BSTs) are an important data structure in computer science used to efficiently store and organise large data sets. They are commonly used in many applications, including database management systems, web search engines, and computer graphics. When working with BSTs, it is often necessary to compare them to determine whether they are identical. In this article, we will explore the concept of identical BSTs and present a simple approach to check whether two given BSTs are identical or not. We will also provide examples to illustrate the process and discuss the implications of this technique.

First, we will discuss the problem statement, algorithm, and then the corresponding C++ and java code.

Problem Statement

Given two Binary Search Trees (BSTs), we have to write a program to determine whether they are identical.

Identical BSTs have the same structure, the same values for each node, and the same key-value pairs. The program should take two BSTs as input and return a Boolean value indicating whether or not the two trees are identical.

The program should run efficiently and should be able to handle large trees.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Problem Explanation

The above problem statement requires us to determine whether two Binary Search Trees are identical or not.

To solve this problem, we need to traverse both trees simultaneously and compare the values of the corresponding nodes. We can use any of the traversal algorithms, such as in-order, pre-order, or post-order traversal.

If we find a mismatch between the nodes of the two BSTs, then we can conclude that the trees are not identical.

The program should take two Binary Search Trees as input and return a Boolean value indicating whether or not the two trees are identical. The solution should be efficient and should be able to handle large trees.

Example 1: Let's consider the following two Binary Search Trees:

BST 1

BST 2

In this example, both BSTs have the same structure, the same values for each node, and the same key-value pairs. Therefore, the two BSTs are identical.

Example 2: Let's consider the following two Binary Search Trees:

BST 1

BST 2

In this example, both BSTs have different structures at the root right node. Therefore, the two BSTs are not identical.

Approach

To solve the problem of determining whether two Binary Search Trees (BSTs) are identical or not, we can use a recursive approach that traverses both trees simultaneously and compares the corresponding nodes.

The basic idea is to traverse both trees in a similar order:

In-order

Pre-order

Post-order

And compare the corresponding nodes of both trees.

To understand in-order, pre-order, or post-order, refer to this article. Traversal in Binary Tree

If the corresponding nodes' values are different, we can conclude that the two trees are not identical. If we reach the end of both trees without finding any mismatch, then we can conclude that the two trees are identical.

Algorithm

Here are the steps to solve this problem:

Check if both roots are null: If both the roots are null, then the two trees are identical. Return true.

Check if only one root is null: If one root is null and the other is not null, then the two trees are not identical. Return false.

Check if the data of the roots is not the same: If the data of the roots is not the same, then the two trees are not identical. Return false.

Recursively check the left and right subtrees: If the data of the roots is the same, then recursively check the left and right subtrees of both trees.

This can check by In-order, Pre-orderorPost-order.

Return the result of the recursive call: If both the recursive calls return true, then the two trees are identical. Otherwise, the two trees are not identical.

We can check it by any method.

For example:

Preorder traversal: The preorder traversal of the tree would be: 5, 3, 2, 4, 7, 6, 8 for both so that it will return true.

Inorder traversal: The inorder traversal of the tree would be: 2, 3, 4, 5, 6, 7, 8 for both so that it will return true.

Postorder traversal: The postorder traversal of the tree would be: 2, 4, 3, 6, 8, 7, and 5 for both so that it will return true.

#include<bits/stdc++.h>
using namespace std;
class CNode {
public:
int val;
CNode* left;
CNode* right;
CNode(int x) : val(x), left(NULL), right(NULL) {}
// Constructor to initialize a CNode object
};
// Function to check if two binary search trees are identical or not
bool isIdentical(CNode* root1, CNode* root2) {
if (root1 == NULL && root2 == NULL) {
// If both roots are NULL, the trees are identical
return true;
}
else if (root1 == NULL || root2 == NULL) {
// If only one root is NULL, the trees are not identical
return false;
}
else if (root1->val != root2->val) {
// If the values of the roots are different, the trees are not identical
return false;
}
else {
// Recursively check the left and right subtrees
return isIdentical(root1->left, root2->left) && isIdentical(root1->right, root2->right);
}
}
int main() {
// Create the first BST
CNode* root1 = new CNode(5);
root1->left = new CNode(3);
root1->right = new CNode(7);
root1->left->left = new CNode(2);
root1->left->right = new CNode(4);
root1->right->left = new CNode(6);
root1->right->right = new CNode(8);
// Create the second BST
CNode* root2 = new CNode(5);
root2->left = new CNode(3);
root2->right = new CNode(7);
root2->left->left = new CNode(2);
root2->left->right = new CNode(4);
root2->right->left = new CNode(6);
root2->right->right = new CNode(8);
if (isIdentical(root1, root2)) {
cout << "The two BSTs are identical" << endl;
}
else {
cout << "The two BSTs are not identical" << endl;
}
// Free the memory used by the CNode objects
delete root1;
delete root2;
return 0;
}

Output

Implementation in Java

class CNode {
public int val;
public CNode left;
public CNode right;
public CNode(int x) {
val = x;
}
}
public class Solution {
// Function to check if two binary search trees are identical or not
public static boolean isIdentical(CNode root1, CNode root2) {
if (root1 == null && root2 == null) {
// If both roots are null, the trees are identical
return true;
} else if (root1 == null || root2 == null) {
// If only one root is null, the trees are not identical
return false;
} else if (root1.val != root2.val) {
// If the values of the roots are different, the trees are not identical
return false;
} else {
// Recursively check the left and right subtrees
return isIdentical(root1.left, root2.left) && isIdentical(root1.right, root2.right);
}
}
public static void main(String[] args) {
// Create the first BST
CNode root1 = new CNode(1);
root1.left = new CNode(2);
root1.right = new CNode(3);
root1.left.left = new CNode(4);
root1.left.right = new CNode(5);
root1.right.left = new CNode(6);
root1.right.right = new CNode(7);
// Create the second BST
CNode root2 = new CNode(1);
root2.left = new CNode(2);
root2.right = new CNode(3);
root2.left.left = new CNode(4);
root2.left.right = new CNode(5);
root2.right.left = new CNode(6);
root2.right.right = new CNode(7);
if (isIdentical(root1, root2)) {
System.out.println("The two BSTs are identical");
} else {
System.out.println("The two BSTs are not identical");
}
}
}

Output

Explanation

The CNode class represents a node in the binary tree with an integer value and two child nodes, left and right. The isIdentical method takes two CNode parameters, root1 and root2, representing the roots of two BSTs, and returns a boolean value indicating whether the trees are identical or not.

The method works by first checking if both roots are null. If they are, the trees are identical, and the method returns true. If only one root is null, the trees are not identical, and the method returns false. If neither root is null, then the method checks if the values of the roots are different. If they are, the trees are not identical, and the method returns false. Otherwise, the method recursively checks the left and right subtrees of both BSTs to determine if they are identical.

The main method creates two BSTs by initialising their roots and child nodes with integer values. The isIdentical method is called with the two BST roots as parameters, and the output is printed based on whether the method returns true or false.

Complexity Analysis

Time Complexity

O(N), where N is the number of nodes in the BST.

Reason: This is because we are visiting each node in both BSTs exactly once.

Space Complexity

O(H), where H is the height of the tree.

Reason: This is because the function uses a recursive approach and the maximum number of recursive calls on the call stack is equal to the height of the tree.

Is it possible for two binary search trees to be identical but have different root nodes?

No, two binary search trees can only be identified if they have the same structure and their corresponding nodes have the same values, including the root node.

How does the time complexity of binary search compare to linear search?

In the worst case, binary search has a time complexity of O(log n), while linear search has a time complexity of O(n). This means that binary search is generally faster than linear search for large datasets.

Can a binary search tree contain duplicate values?

It depends on the implementation. In some cases, binary search trees allow for duplicate values, while in others, they do not. This can affect the behaviour of various operations, such as insertion and search.

What is the role of a node in a binary search tree?

A node in a binary search tree represents a value and contains references to its left and right children, which are also nodes. The tree structure is defined by the relationships between nodes, which are organised based on their values.

How does a binary search tree differ from a heap data structure?

While both data structures are based on trees, a binary search tree maintains an ordered structure based on its nodes' values. At the same time, a heap is optimised for efficiently extracting the minimum or maximum value from a data set. Additionally, a heap typically has fewer restrictions on its structure and may not maintain a strict ordering.

Conclusion

This article taught us how to check whether two binary search trees (BSTs) are identical. We learned that two BSTs are identical if they have the same structure and their corresponding nodes have the same values. We also discussed an algorithm to check the equality of two BSTs and implemented it in both C++ and Java programming languages.

We saw that the algorithm is a recursive function that visits each node in both BSTs exactly once, comparing their values to determine if they are equal.

Below are more links related to the DSA topic that will help you to build your skill:

Apart from this, you can practice a wide range of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, we can also find the interview experience of scholars working in renowned product-based companies here.