Check if two binary search trees are identical given their array representations | Set 2

Given two arrays which would be used to construct two different binary search trees(BSTs), write a prgram to identify if the BSTs constructed from these would be identical. The condition is that the program should be able to identify this without actually building BSTs.

For example, using array {3,5,4,6,1,0,2} the BST constructed would be  -

You can verify that using array {3,1,5,2,4,6,0} the same BST would be constructed.

In the following example though, the BST constructed using array {6,9,8} is not same as the BST constructed using array {6,8,9}.


Video coming soon!



Subscribe for more updates


Preparing for interviews? IDeserve team is here to help.




Algorithm/Insights

In this post we have looked at an algorithm to solve the same problem which runs in O(n) time and O(1) space. We think that the algorithm that we will go through now is more intuitive than the algorithm in the previous post.

The idea that this algorithm is based on is that - if we are given an array out of which we need to construct the BST, then the root of the BST would be constructed from the element present at the 0th index of the given array, left sub-tree would be constructed from the elements in the array which are less than the element used to construct root and right sub-tree would be constructed from the elements in the array which are greater than the element used to construct root.

The steps of the algorithm with input as array1 and array2 are -
1. Check if size of array1 is equal to size of array2. If not then the BSTs constructed would definitely be different and hence return false.
2. Check if size of both arrays is 0. If it is then BSTs constructed from both arrays would be null BSTs and hence return true.

Step #1 and #2 are base cases for this recursive algorithm.
3. Now check if array1[0] is equal to array2[0]. This steps helps to check if root node values for both BSTs are same.

If algorithm passes condition in step #3, then we need to check if left and right sub-trees for this root are also same. Note that left and right sub-trees would also be BSTs themselves and therefore we can make recursive calls for checking that.
4. Create an array - array1Left using elements from array1 which are less than array1[0]. These elements would basically be used to create left sub-tree for root with value array1[0]. Also create array1Right using elements from array1 which are greater than array1[0].
5. Similar to step #4, create arrays array2Left and array2Right from elements of array2 using array2[0] as the root node value.
6. Now make a recursive call to this same function by passing array1Left and array2Left as its arguments to check if left sub-trees(with root value as array1[0]) created would be identical.
7. If left sub-trees are same, then again make a recursive call to this same function but with arguments array1Right and array2Right. This step is for checking if right sub-trees(with root value as array1[0]) created would be identical.  
8. If step #6 and #7 are true then the algorithm returns true otherwise false.

Please check function checkIfSameBSTs(ArrayList listForTree1, ArrayList listForTree2) which has more comments to help understand the implementation details.

For the input arrays {3,5,4,6,1,0,2} and {3,1,5,2,4,6,0}, BSTs would be constrcuted as shown below. Please note that these BSTs are not actually constructed but we have shown them just to illustrate the above algorithm. Note how 0th element of every sub-array on the left hand side matches with the 0th element of corresponding sub-array on the right hand side. That is precisely the base case in the above algorithm.

Time complexity of this algorithm is O(n^2) in worst case and space complexity is O(n).

Please add comments below in case you have any feedback/queries.


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.nilesh;

import java.util.ArrayList;
/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Checks if identical BSTs without building them in time O(n^2) and space O(n). 
 * @author Nilesh
 */

public class CheckIdenticalBSTs 
{
    boolean checkIfSameBSTs(ArrayList<Integer> listForTree1, ArrayList<Integer> listForTree2)
    {
        // both trees should have same size
        if (listForTree1.size() != listForTree2.size())
        {
            return false;
        }
        
        // if both trees are null trees
        if (listForTree1.size() == 0)
        {
            return true;
        }
        
        // root node has to be the same
        if (listForTree1.get(0) == listForTree2.get(0))
        {
            // segregate nodes for left and right sub-trees for both trees
            ArrayList<Integer> listForLeftTree1 = new ArrayList();
            ArrayList<Integer> listForRightTree1 = new ArrayList();
            
            ArrayList<Integer> listForLeftTree2 = new ArrayList();
            ArrayList<Integer> listForRightTree2 = new ArrayList();
            
            for (int i = 1; i < listForTree1.size(); i++)
            {
                if (listForTree1.get(i) < listForTree1.get(0))
                {
                    listForLeftTree1.add(listForTree1.get(i));
                }
                else
                {
                    listForRightTree1.add(listForTree1.get(i));
                }
                
                if (listForTree2.get(i) < listForTree2.get(0))
                {
                    listForLeftTree2.add(listForTree2.get(i));
                }
                else
                {
                    listForRightTree2.add(listForTree2.get(i));
                }
            }
            
            // and check that left and right sub-tree are also same
            return checkIfSameBSTs(listForLeftTree1, listForLeftTree2) &&
                   checkIfSameBSTs(listForRightTree1, listForRightTree2);
        }
        
        return false;
    }
    
    boolean checkIfSameBSTs(int[] arrayForTree1, int[] arrayForTree2)
    {
        if (arrayForTree1.length != arrayForTree2.length)
        {
            return false;
        }
        
        ArrayList<Integer> listForTree1 = new ArrayList();
        ArrayList<Integer> listForTree2 = new ArrayList();
        
        for (int i = 0; i < arrayForTree1.length; i++)
        {
            listForTree1.add(arrayForTree1[i]);
            listForTree2.add(arrayForTree2[i]);
        }
        return checkIfSameBSTs(listForTree1, listForTree2);
    }
    
    public static void main(String[] args) 
    {
        CheckIdenticalBSTs solution = new CheckIdenticalBSTs();
        
        int[] arrayForTree1 = {3,5,4,6,1,0,2};
        
        int[] arrayForTree2 = {3,1,5,2,4,6,0};
        
        System.out.println("Check if identical BSTs: " + solution.checkIfSameBSTs(arrayForTree1, arrayForTree2));
    }
}
		

Order of the Algorithm

Time Complexity is O(n^2)
Space Complexity is O(n)


Contribution

  • Sincere thanks from IDeserve community to Nilesh More for compiling current post.

    Nilesh More

    Ninja Programmer