Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 🥳
2.
Problem Statement 🧾
3.
Examples
4.
Approach
4.1.
Algorithm
4.2.
Example
4.3.
Implementation in C++
4.3.1.
Output
4.3.2.
Time Complexity ⌛
4.3.3.
Space Complexity 🚀
5.
Frequently Asked Questions
5.1.
What is a binary tree?
5.2.
What is a binary search tree?
5.3.
What is a Full Binary Tree?
5.4.
Why is Binary Search Tree used?
5.5.
Which property of BST is used to check for identical BSTs without building the trees?
6.
Conclusion
Last Updated: Mar 27, 2024
Hard

Check for Identical BSTs Without Building the Trees

Author Ayushi Goyal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction 🥳

A binary search tree is a tree in which all nodes left to the root node have values less than the root node, and all nodes right to the root node have values greater than the root node. The other difference is all of the subtrees in the binary search tree are themselves a binary search tree.

Introduction

This blog will discuss a simple DSA problem: Check for identical BSTs without building the trees.

Problem Statement 🧾

The problem "Check for identical BSTs without building the trees" states that you are given two arrays representing some nodes. So we created BSTs from both of these arrays, and now we need to check if the BSTs created from these arrays are identical or not. The complication here is that we cannot create the trees (i.e., we cannot create and then compare them). We need to check if these arrays are identical or not without constructing a tree.

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

Examples

Example 

Input: 

Arr1[] = {2, 5, 4, 6, 1}

Arr2[] = {2, 1, 5, 4, 6}

example tree

Output: Yes, Arrays are identical

Approach

To check for identical BSTs without building the trees, we will use some basic properties of binary search trees: all elements in the left subtree are smaller than the root node. At the same time, all elements on the right are larger than the root node.  

Algorithm

  1. Firstly we will check if the size of both the arrays is different, then BSTs formed can't be identical.
     
  2. Check if the size of the array is 0, then return true.
     
  3. If the above two conditions are false, then we will check if the root of both the trees is the same by checking if 'array1[0]' is equal to 'array2[0]'.
     
  4. If the 3rd condition is true, then we recursively for left and right subtree by doing the following:
  • Create ‘array_left1’ and ‘array_right1’ using elements of ‘array1’,  ‘array_left1’ contain elements of ‘array1’ which are less than root node, and ‘array_right1’ contain elements which are greater than root.
     
  • Similarly, for ‘array2’, create ‘array_left2’ and ‘array_right2’ using elements of ‘array2’,  ‘array_left2’ contain elements of ‘array2’ which are less than the root node, and ‘array_right2’ contains elements that are greater than root.
     
  • Make a recursive call for ‘array_left1’ and ‘array_left2’ to check for the left subtree.
     
  • Another recursive call for ‘array_right1’ and ‘array_right2’ for checking the right subtree.
     
  • If the result of conditions C and D is true, then return true otherwise, return false. 

Example

Let's now discuss working through an example, and then we will code it: 

example

Iteration 1:

  • Check size of arrays, Size of array1 = 7 = Size of array2
  • Check root element 
root check 1
  • Array separation after the first recursion call will be 

iteration 1

As shown in the image 

array_left1 = [1,0,2]

array_right1 = [5,4,6]

array_left2 = [1,2,0] 

array_right2 = [5,4,6]
 

Iteration 2 : 

Call function for array_left1 and array_left2 

So now array1 = array_left1 = [1,0,2] and array2 = array_left2 = [1,2,0].

  • Check size if arrays, Size of array1 = 3 = Size of array2
  • Check root element 
root check 2
  • Array separation after the next recursion call for the left subtree will be

iteration 2

As the left subtree is identical for array1 and array2, so left = true.
 

Iteration 3: 

Call function for array_right1 and array_right2 

So now array1 = array_right1 = [5,4,6] and array2 = array_right2 = [5,4,6].

  • Check size if arrays, Size of array1 = 3 = Size of array2
  • Check root element 
root check 3
  • Array separation after the next recursion call for the right subtree will be 

iteration 3

As the right subtree is identical for array1 and array2, so right = true.

Both right and left are true so return true to the main function call.

Implementation in C++

// A C++ program = check for identical BSTs without building the trees
#include<bits/stdc++.h>
using namespace std;

bool checkBST(vector<int>arr1, vector<int>arr2)
{
    // Calculate size of both arrays
    int n = arr1.size();
    int m = arr2.size();
    
    // Check if size is different 
    if(n != m)
    return false;
    
    // Check if size is zero
    if(n == 0)
    return true;
    
    // Check for root node
    if(arr1[0] == arr2[0])
    {
        vector<int>array_left1;
        vector<int>array_right1;
        vector<int>array_left2;
        vector<int>array_right2;
        
        for(int i=1;i<n;i++)
        {
            
            // Adding elements in left subtree of arr1
            if(arr1[i] < arr1[0])
            array_left1.push_back(arr1[i]);
            
            // Adding elements in left subtree of arr1
            else
            array_right1.push_back(arr1[i]);
            
            // Adding elements in left subtree of arr2
            if(arr2[i] < arr2[0])
            array_left2.push_back(arr2[i]);
            
            // Adding elements in left subtree of arr2
            else
            array_right2.push_back(arr2[i]);
        }
        
        bool left = checkBST(array_left1, array_left2);
        bool right = checkBST(array_right1, array_right2);
        
        return left && right;
    }
    
    // If all conditions are false then return false
    return false;
}

int main()
{
    // Declaring two arrays 
vector<int>arr1;
vector<int>arr2;

// Calculate the size of both arrays 
int n,m;
cout<<"Enter size of arrays : ";
cin>>n>>m;

cout<<"Enter elements of array 1 - ";
for(int i=0;i<n;i++)
{
    int x;
    cin>>x;
    arr1.push_back(x);
}

cout<<"Enter elements of array 2 - ";
for(int i=0;i<m;i++)
{
    int x;
    cin>>x;
    arr2.push_back(x);
}

// Check is size of arrays is different 
if(n != m)
{
    cout << "No, Arrays are not identical";
    exit(0);
}

if(checkBST(arr1, arr2))
cout << "Yes, Arrays are identical";

else
cout << "No, Arrays are not identical";

return 0;
}

Output

Output

Time Complexity ⌛

 

Time complexity

The time complexity of the problem “Check for identical BSTs without building the trees” using the above approach is O(N), for traversing both arrays, where N is the number of elements in the array. 

Space Complexity 🚀

Space complexity

The space complexity of the problem “Check for identical BSTs without building the trees” using the above approach is O(N) for two arrays of size N.
Check out this problem - Largest BST In Binary Tree

Frequently Asked Questions

What is a binary tree?

A binary tree is a data structure having a maximum of two children. There can only be two children per element in a binary tree; hence we usually refer to them as the left and right children.

What is a binary search tree?

A binary search tree is a binary tree in which all of the nodes left to the root node have values less than the root node, and all of the nodes right to the root node have values greater than the root node.

What is a Full Binary Tree?

A full binary tree is a particular kind of binary tree in which every parent node and internal node either has two children or none at all.

Why is Binary Search Tree used?

It is beneficial in many scenarios where we have to compare the sorted data then it can be used. 

Which property of BST is used to check for identical BSTs without building the trees?

The property of binary search trees is that all elements in the left subtree are smaller than the root. While all elements on the right of the root are larger than the root is used for solving this problem.

Conclusion

In this article, we have discussed a coding problem in which we have to Check for identical BSTs without building the trees. We have seen the question's solution, time, and space complexity(Check for identical BSTs without building the trees).

If you found this blog has helped you enhance your knowledge about the above question, and if you want to learn more, check out our articles

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. And also, enroll in our courses and refer to the mock test and problems available. Have a look at the interview experiences and interview bundle for placement preparations. Nevertheless, you may consider our paid courses to give your career an edge over others!

Happy Coding!

Previous article
Check if two given key sequences construct the same BSTs
Next article
Number of BSTs
Live masterclass