Check if two given key sequences construct the same BSTs

Sample Examples

Let's look over some examples to get a better understanding. 

Example 1

Consider the following example to begin with. Let's take two arrays as inputs.

Input:

a=[3,4,1,5,2] 
b=[3,1,2,4,5]

 

Output:

True

 

Explanation:

The binary search tree generated from array a=[3,4,1,5,2] looks like

The binary search tree generated from array b=[3,1,2,4,5] looks like

As we can see, both are the same binary search trees, so our result becomes True.

Example 2

Input:

a=[3,1,4,2,5]
b=[3,4,2,1,5]

 

Output:

False

 

Explanation:

The Tree generated from b=[3,4,2,1,5] looks like this:

Whereas the binary search tree generated by a=[3,1,4,2,5] looks like this:

As we can see, the two binary search trees are not the same, so the result is False.

Approach 1

We shall be following the recursive approach here. First, we will generate the corresponding Binary Search Tree from the two arrays. Then we will check if the two trees are the same or not.

Algorithm

Let's go through the approach step by step: 

• First, we'll generate the corresponding binary search tree from the given array.
   
• For generating the binary search tree, we shall be iterating through the values in the list/array and creating a new Tree Node with those values. 
   
• The first value becomes the tree's root, and the upcoming values are assigned to the left or right subtree based on their values. For more information, please refer here. 
   
• Now, after generating the two trees, we shall be traversing both trees simultaneously using recursion and matching the corresponding values of the trees. If they both have the same value, we'll be going further or returning False.
   
• The function isSame(head1, head2) takes two parameters, head1 and head2 (current position of both trees). Now if both reach null or None simultaneously, we'll be returning True (as they have the same structure), or else return False. 
   

If any of the two pointers reaches null or None before the other, their structure is different, so both are not the same trees (return False).

Note: We will also be checking if the values of the two nodes match and return True or False, respectively.

Here is the pseudo-code for our algorithm

Function isSame(p:<node of tree>, q:<node of tree>):
   // base condition
   if p and q are null -> output True
   if p is null -> output False
   if q is null -> output False

# if value of the nodes doesn't match at any instant
   if value of p !== value of q -> output False

# call recursively
   assign left variable to isSame(p.left, q.left)
   assign right variable to isSame(p.right, q.right)
   ans = boolean AND of right and left
   output ans

Dry Run

Now let's look at how this algorithm works on our test cases.

Input:

a=[3,4,1,5,2]
b=[3,1,4,2,5]

 

Explanation:

Let us try to generate the tree using a=[3,4,1,5,2]

Step 1: The first Node becomes the root node, So 3 becomes the root node for the BST.

Step 2: Now enters 4, and since 4 > root of the tree, so it inserts as the right child.

Step 3: Now comes 1, 1 < root of the tree, so it inserts as the left child of 3.

Step 4: Now we have 5, 5 > 3, so it goes to the right side, then 5 > 4, so it becomes the right child of 4.

Step 5: Now the last Node, i.e., 2, 2 < 3, so it goes to the left side, then 2 > 1, so it becomes the right child of 2) 

Step 6: So our generated binary search tree via a=[3,4,1,5,2] will look like this.

Step 7: Similarly, on constructing the binary search tree, using b=[3,1,2,4,5], 

We get:

Now let's traverse the two binary search trees and look at how this algorithm works.

Step 1: Let p be the head pointer of tree1, and q be the head pointer of tree2.

Initially, the values of p and q are p = 3 and q = 3, as both are currently pointing to their respective heads.

Step 2: So we call the function isSame(p,q) with these two values. It first checks if any of the tree's base conditions is/are hitting; if not, it then continues and checks if the value of these two nodes matches.

Step 3: Currently, neither p nor q is null, so it checks whether the values corresponding to these nodes match. They do, as values of p = 3 and q = 3, so we recursively call the left child of both the binary search trees.

Step 4: Now, on calling the left child of both trees, we get p = 1 and q = 1.

Again the same conditions are checked, and we recursively call the left child of both nodes.

Step 5: Now, on calling the left child of both trees, we get p = null and q = null. Now both are null at the same time, so their left structure is the same; hence we encounter the base condition.

if p == null and q == null:
       return True

 

So, we return True from here.

Step 6: Now we have returned True to the left variable in the function body. Now we call the right child of both p = 1  and q = 1; We get p = 2  and q = 2.

Step 7: Again, we call the left child of both p and q. Now p = null & q = null.

We encounter the base condition, i.e., both are reaching null at the same point, so we return True.

Now for p = 1 and q = 1, we have left = True and right = True, so we return 

left and right, i.e., True from both the subtrees whose root is 1.

Step 8: Now, on reaching the root of the tree, p = 3 and q = 3, we can see that the left subtrees of p and q are the same.

Similarly, we will check the right subtree of p and q. Since we return True from every step of recursion, and so both the trees are the same.

Must Read Recursive Binary Search.

Implementation in C++

#include <iostream>
using namespace std;

struct node {
   // structure for a node of tree
   int data;
   node *left;
   node *right;
};
class binary_search_tree {
   // binary search tree class
public:
   // elements are of node datatype
   node *root;

   binary_search_tree(int value) {
       // parameterized constructor
       root = new node;
       root->data = value;
       root->left = NULL;
       root->right = NULL;
   }
   node *create_node(int value) {
       // creates a node
       node *temp = new node;
       temp->data = value;
       temp->left = NULL;
       temp->right = NULL;
       return temp;
   }
   void add(int value) {
       // adds a node
       insert(root, value);
   }
   node *insert(node *link, int value) {
       // inserts a node to the tree
       if (link == NULL) {
           return create_node(value);
       }
       if (value > link->data) {
           // right side
           link->right = insert(link->right, value);
       }
       else {
           // left side
           link->left = insert(link->left, value);
       }
       return link;
   }
};
bool isSame(node *p, node *q) {
   // function to check if the trees are same or not
   if (p == NULL && q == NULL) {
       //  base condition to check the structure of the tree
       return true;
   }

   /*
       if any one of the tree reaches null or None first
       then they are not the same tree
   */
   if (p == NULL || q == NULL)
       return false;

   if (p->data != q->data) {
       // if value of the nodes doesn't match at any instant
       return false;
   }

   bool left = isSame(p->left, q->left);
   bool right = isSame(p->right, q->right);

   return right && left;
}
int main() {
   // driver code
   int a[5] = {3, 4, 1, 5, 2};
   int b[5] = {3, 1, 4, 2, 5};

   // creating trees
   binary_search_tree b1(a[0]);
   binary_search_tree b2(b[0]);

   // adding values to both trees
   for (int i = 1; i < 5; i++) {
       b1.add(a[i]);
       b2.add(b[i]);
   }

   // checking if the trees are same
   if (isSame(b1.root, b2.root)) {
       cout << "True" << endl;
       return 0;
   }
   cout << "False" << endl;
   return 0;
}

 

Output:

Implementation in Java

class Node {
   // class for node of binary search tree
   int val;
   Node left, right;

   public Node(int data) {
       // parameterized constructor
       val = data;
       left = null;
       right = null;
   }
}

class BinarySearchTree {

   // BST root node
   Node root;

   BinarySearchTree() {
       // default constructor
       root = null;
   }

   void add(int val) {
       // add a node to BST
       root = insert(root, val);
   }

   Node insert(Node root, int val) {
       // base condition
       if (root == null) {
           root = new Node(val);
           return root;
       }

       // if node is less than root, then left

       if (val < root.val) // insert in the left subtree
           root.left = insert(root.left, val);

       else if (val > root.val) // insert in the right subtree
           root.right = insert(root.right, val);

       return root;
   }
}

class Main {
   public static boolean isSame(Node p, Node q) {
       // function to check if the trees are same or not
       if (p == null && q == null) {
           // base condition to check the structure of the tree
           return true;
       }

       /*
        * if any one of the tree reaches null or None first
        * then they are not the same tree
        */
       if (p == null || q == null)
           return false;

       if (p.val != q.val) {
           // if value of the nodes doesn't match at any instant
           return false;
       }

       boolean left = isSame(p.left, q.left);
       boolean right = isSame(p.right, q.right);

       return right && left;
   }

   public static void main(String[] args) {
       // create a BST object
       BinarySearchTree tree_a = new BinarySearchTree();

       int[] a = new int[] { 3, 4, 1, 5, 2 };
       tree_a.add(a[0]);

       // add values to tree
       for (int i = 1; i < a.length; i++) {
           tree_a.add(a[i]);
       }

       BinarySearchTree tree_b = new BinarySearchTree();
       int[] b = new int[] { 3, 1, 2, 4, 5 };

       tree_b.add(b[0]);

       // add values to tree
       for (int i = 1; i < a.length; i++) {
           tree_b.add(b[i]);
       }

       if (isSame(tree_a.root, tree_b.root)) {
           System.out.println("True");
           return;
       }
       System.out.println("False");
       return;
   }
}

 

Output:

Implementation in Python

class Node:
   """
   Definition of a node for binary search tree.
   """

   def __init__(self, val=0, left=None, right=None) -> None:
       # Initializes the node with value, left child, and right child

       self.val = val
       self.left = left
       self.right = right


def isSame(p: Node, q: Node) -> bool:
   # function to check if the trees are same or not

   if p is None and q is None:
       # base condition to check the structure of the tree
       return True

   # if any one of the tree reaches null or None first
   # then they are not the same tree
   if p is None or q is None:
       return False

   if p.val != q.val:
       # if value of the nodes doesn't match at any instant
       return False

   left = isSame(p.left, q.left)
   right = isSame(p.right, q.right)

   return right and left


def insert(node: Node, val: int) -> Node:
   if not node:
       # base case
       return Node(val)

   if node.val > val:
       node.left = insert(node.left, val)
   elif node.val < val:
       node.right = insert(node.right, val)
   return node


# main
a = [3, 4, 1, 5, 2]
b = [3, 1, 4, 2, 5]

# making two root nodes
root_a = insert(None, a[0])
root_b = insert(None, b[0])

# traversing through the array
# to generate binary search tree
for key in a[1:]:
   insert(root_a, key)
for key in b[1:]:
   insert(root_b, key)

# final result
print(isSame(root_a, root_b))

 

Output:

Complexity Analysis

• Time Complexity: O(n²) is the worst-case time complexity, where n is the maximum length among the two arrays. As seen above, we will be traversing through the array, and inserting the elements in the tree. Insertion to a Binary Search Tree in the worst case may reach O(n), and since we are traversing the array to add elements in the tree, in the worst case scenario, it runs O(n²).
   
• Space Complexity: For creating a tree and storing its values, the space complexity reaches O(n), where "n" is the number of nodes in the tree.

Approach 2

In this approach, we shall be traversing the arrays and recursively determining if the trees constructed are the same or not. We won’t be constructing a Binary Search Tree from the values and will be determining if they are the same via simple traversal of arrays. 

Algorithm

We will be determining whether the trees will be the same without the actual construction of the trees. Here’s what we’ll be doing

• First, we will check if the two arrays are of the same length or not. If not, then we have fewer elements in one of the trees, so they won’t be constructing the same Binary Search Tree.
   
• Then, if they are of the same length, we will check whether the roots of both trees are the same. This can be done by checking the first element of both arrays.
   
• If both the above conditions are not satisfied, then we’ll be checking whether the children of any node of both trees are of the same values and follow the same pattern.
   
• This can be done by creating two lists, one containing the elements smaller than the node and the other containing the elements greater than the node. These two lists represent the left subtree and right subtree of a particular node. Now, we have to check if the arrays are the same.
   
• Then we will recursively check the same conditions for all the elements of the array. If all conditions are satisfied, then they construct the same Binary Search Tree. 

Dry Run

Now let’s look at how the above algorithm works with the help of a dry run.

Input:

a=[3,4,1,5,2]
b=[3,1,4,2,5]

 

Output:

True

 

Explanation: 

Let’s walk through it step by step and follow the above algorithm. 

Step 1: Check if the two lengths of the arrays are the same. For array a, the length is 5, and for array b, the length is also 5. So the two lengths are the same. Now we’ll proceed to the next step.

Step 2: As we can see, a[ 0 ] = 3 and b[ 0 ] = 3, so the root element of both are the same. We’ll proceed to the next step. 

Step 3: Let’s create two lists, namely left_subtree and right_subtree, where we will be appending values less than the node to the left_subtree and values greater than the node will be appended to the right_subtree. 

Step 4: Now call the function again for the left_subtree and the right_subtree. Since both are same, our function will return true.

Implementation in C++

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

bool isSame(vector<int> tree1, vector<int> tree2) {
    // if the subtrees are same then return True
    if (tree1 == tree2) return true;

    /*
    if structure of the tree does not match
    return False
    */
    if (tree1.size() != tree2.size()) return false;

    // root does not match
    if (tree1[0] != tree2[0]) return false;

    // filling the subtrees
    vector<int> left_subtree1, left_subtree2, right_subtree1, right_subtree2;

    // current root of the subtrees
    int root1 = tree1[0];
    int root2 = tree2[0];

    // generating subtrees via inorder
    for (int i = 1; i < tree1.size(); i++) {
        int node1 = tree1[i];
        if (node1 < root1) left_subtree1.push_back(node1);
        else right_subtree1.push_back(node1);

        int node2 = tree2[i];
        if (node2 < root2) left_subtree2.push_back(node2);
        else right_subtree2.push_back(node2);
    }

    // checking the left and right subtree simultaneously
    bool left = isSame(left_subtree1, left_subtree2);
    bool right = isSame(right_subtree1, right_subtree2);
    return left and right;
}

int main() {
    // input
    vector<int> tree1 = {3, 4, 1, 5, 2};
    vector<int> tree2 = {3, 1, 4, 2, 5};

    if (isSame(tree1, tree2)) cout << "True" << endl;
    else cout << "False" << endl;

    return 0;
}

 

Output

Implementation in Java

import java.util.ArrayList;

class Main {
    public static boolean isSame(ArrayList<Integer> tree1, ArrayList<Integer> tree2) {
        // if the subtrees are same then return True
        if (tree1.equals(tree2))  return true;


        // if structure of the tree does not match
        // return False
        if (tree1.size() != tree2.size())
            return false;
        if (tree1.get(0) != tree2.get(0))
            return false;


        // filling the subtrees
        ArrayList<Integer> left_subtree1 = new ArrayList<>();
        ArrayList<Integer> left_subtree2 = new ArrayList<>();
        ArrayList<Integer> right_subtree1 = new ArrayList<>();
        ArrayList<Integer> right_subtree2 = new ArrayList<>();


        // current root of the subtrees
        int root1 = tree1.get(0);
        int root2 = tree2.get(0);

        // generating subtrees via inorder
        for (int i = 1; i < tree1.size(); i++) {
            int node1 = tree1.get(i);
            if (node1 < root1) left_subtree1.add(node1);
            else right_subtree1.add(node1);

            int node2 = tree2.get(i);
            if (node2 < root2) left_subtree2.add(node2);
            else right_subtree2.add(node2);
        }

        // checking the left and right subtree simultaneously
        boolean left = isSame(left_subtree1, left_subtree2);
        boolean right = isSame(right_subtree1, right_subtree2);
        return left && right;
    }


    public static void main(String[] args) {
        // input
        ArrayList<Integer> tree1 = new ArrayList<>();
        tree1.add(3);
        tree1.add(4);
        tree1.add(1);
        tree1.add(5);
        tree1.add(2);

       ArrayList<Integer> tree2 = new ArrayList<>();
        tree2.add(3);
        tree2.add(1);
        tree2.add(4);
        tree2.add(2);
        tree2.add(5);

        if (isSame(tree1, tree2)) System.out.println("True");
        else System.out.println("False");
    }
}

 

Output

Implementation in Python

def isSame(tree1, tree2):
    # base conditon
    if tree1 == tree2:
        return True
   
    # structure of the trees does not match
    if len(tree1) != len(tree2):
        return False
   
    if tree1[0] != tree2[0]:
        return False
 
    # filling the subtrees
    left_subtree1, left_subtree2, right_subtree1, right_subtree2 = [], [], [], []

    # current root of the subtrees
    root1, root2 = tree1[0], tree2[0]

   # generating subtrees via inorder
    for i in range(1, len(tree1)):
        node1 = tree1[i]
        if node1 < root1:
            left_subtree1.append(node1)
        else:
            right_subtree1.append(node1)

        node2 = tree2[i]
        if node2 < root2:
            left_subtree2.append(node2)
        else:
            right_subtree2.append(node2)
 
   # checking the left and right subtree simultaneously
    left = isSame(left_subtree1, left_subtree2)
    right = isSame(right_subtree1, right_subtree2)
    return left and right


# input
tree1 = [3, 4, 1, 5, 2]
tree2 = [3, 1, 4, 2, 5]
print(isSame(tree1, tree2))

 

Output

Complexity Analysis

Here we will check the complexity of our approach

• Time complexity: As we are creating new arrays, and traversing them again and again, so if n represents the length of the tree, then our Time complexity reaches O(n²).
   
• Space complexity: We are creating two new arrays at every step, and each can contain max elements of n, which is the length of the tree. So our worst-case space complexity reaches O(n).

Frequently Asked Questions

What is a Binary Search Tree?

A Binary Seach Tree belongs to the tree data structure where each Node can have at max two children. The child having values less than the parent node goes into the left subtree, while the others go into the right subtree.

How to search any element in a Binary Search Tree?

We can perform a binary search to search our element in the tree. We call the recursive function and check if the value of key > Node.val, if yes, then go to the right subtree; else, go to the left subtree.

How to insert elements into a Binary search tree? 

Elements can be added to the binary search tree, recursively or iteratively. This is similar to searching for an element in Binary Search Tree. If the value is not found, we just add the value.

How to implement Binary Search Tree in C++?

We make a class called Node which represents the Node of the tree. It has three attributes, namely val, left, and right. The val contains the Node's value, while left and right are the addresses of the left and right tree nodes.

How to check if two trees are the same?

We can check it recursively; we go through the nodes of the trees recursively and check if their structures are the same. Alongside this, we also check if the Node's values are equal or not. If all tests pass, then the trees are the same.

Conclusion

We figured out how to check if any two sequences generate the same Binary Search Tree. We have seen how to construct a binary search tree, how to check if two trees are the same via recursion, and how to implement the same in Python, C++, and Java.

We hope this has helped you to increase your understanding of Binary Search Trees and how to check if trees are the same. If you want to learn more about such topics, do read more of our articles.

• Introduction to Binary Search Trees
• Insertion in Binary Search Trees
• Insertion in Binary Search Trees (Iteratively)
• Operations in Binary Search Trees
• Shortest distance between two nodes in Binary Search Trees

 

Suppose you want to know more about Binary Search Trees or other DSA topics. Refer to our Guided Path to upskill yourself in DSA, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundles for placement preparations.

However, you may consider our paid courses to give your career an edge over others!

Happy Learning!