Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Difficulty: Medium

Find if the given array of size n can represent BST of n levels or not

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

Hi Ninja🥷! In this article, we will learn to solve the problem to Find if the given array of size n can represent BST of n levels or not. We will learn different approaches to solve this problem. We will start with a basic brute force approach to constructing BST and proceed further with the better and optimal approach, which takes less time and space without constructing the whole BST. I hope you will enjoy and have fun learning a medium-level DSA problem to find if the given array of size n can represent BST of n levels or not.

Problem Description

The problem is to find if the given array of size n can represent BST of n levels or not. That is, you have been given an array of size n. You have to find if the given array can represent BST of n levels or not.

Sample Examples

Input 1

550, 250, 140, 300, 150

 

Output

No

 

Explanation:

example1

 

Input 2

5223, 3400, 883, 1211, 990

 

Output

Yes

 

Explanation:

example2

Method 1: By Constructing Binary Search Tree

A basic approach would be to form a tree from the given array and check whether that tree is BST or not.

Algorithm

  • We start traversing the given array and form a tree from it.
  • We make nodes and insert all array elements level by level in the tree. 
  • To insert an element: We check If the current element is less than the previous value or greater. After constructing the tree, we check if the constructed tree is a BST or not.

C++ code

//Find if the given array of size n can represent BST
//of n levels or not
#include <bits/stdc++.h>
using namespace std;


// structure for Node of binary tree
struct Node {
    int value;
    struct Node *right;
    struct Node *left;
};


Node* newnode(int value)
{
    Node* temp = new Node;
    temp->value = value;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}


// To create a Tree with n levels. We always
// insert a new node to the right if it is greater than the previous value
// insert new node to left if it is smaller than the previous value
Node* createTree(int arr[], int n)
{
        Node* root = newnode(arr[0]);
        Node* temp = root;
    for (int j = 1; j < n; j++) 
    {
        if (temp->value > arr[j]) {
            temp->left = newnode(arr[j]);
            temp = temp->left;
        }
        else {
            temp->right = newnode(arr[j]);
            temp = temp->right;
        }
    }
    return root;
}


//This function checks whether the tree is BST or not
bool isBST(Node* root, int mi, int ma)
{
    if (root == NULL)
    return true;

    if (root->value < mi || root->value > ma)
    return false;

    return (isBST(root->left, mi,
    (root->value) - 1)
    && isBST(root->right,
    (root->value) + 1, ma));
}


bool RepresentNLevelBSTorNot(int arr[], int n)
{
    Node* root = createTree(arr, n);
    return isBST(root, INT_MIN, INT_MAX);
}


// main function
int main()
{
    int arr[] = { 5223, 3400, 883, 1211, 990 };
    int n = sizeof(arr) / sizeof(arr[0]);
    
    if (RepresentNLevelBSTorNot(arr, n))
    cout << "Yes";
    else
    cout << "No";
    
    return 0;
}

 

Output

Yes

JAVA code

//Find if the given array of size n can represent BST
//of n levels or not
class BinaryTree
{


    // structure for Node of Binary Tree
    static class Node
    {
        int value;
        Node right;
        Node left;
    };
    
    
    static Node newnode(int value)
    {
        Node temp = new Node();
        temp.value = value;
        temp.left = null;
        temp.right = null;
        return temp;
    }
    
    
    // To create a Tree with n levels. We always
    // insert a new node to the right if it is greater than the previous value
    // insert a new node to the left if it is smaller than the previous value.
    static Node createTree(int arr[], int n)
    {
        Node root = newnode(arr[0]);
        Node temp = root;
        for (int i = 1; i < n; i++)
        {
            if (temp.value > arr[i])
            {
                temp.left = newnode(arr[i]);
                temp = temp.left;
            }
            else
            {
                temp.right = newnode(arr[i]);
                temp = temp.right;
            }
        }
    return root;
    }
    
    
    //This function checks whether the tree is BST or not
    static boolean isBST(Node root, int mi, int ma)
    {
        if (root == null)
        return true;
    
        if (root.value < mi || root.value > ma)
        return false;
    
        return (isBST(root.left, mi,
        (root.value) - 1)
        && isBST(root.right,
        (root.value) + 1, ma));
    }
    
    
    //this function will
    //find if the given array of size n can represent BST
        //of n levels or not
    static boolean canRepresentNLevelBST(int arr[], int n)
    {
        Node root = createTree(arr, n);
        return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }


// main
    public static void main(String[] args)
    {
        int array[] = {5223, 3400, 883, 1211, 990};
        int n = array.length;
    
    
        if (canRepresentNLevelBST(array, n))
        {
            System.out.println("Yes");
        }
        else
        {
            System.out.println("No");
        }
    }
}

 

Output

Yes

Complexity Analysis

Time Complexity: O(N), Where N is the size of given array. We traverse the array once and make levels from the values, traversing the array takes O(N) time. At last we call isBST function to check if it is BST or not, this function takes O(N) time.

Space Complexity: O(H), Where H is the height of the binary tree, the extra space is used due to the function call stack.

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

Method 2: without constructing Binary Search Tree

Algorithm

We have to create two variables: 

ma = INT_MAX to check the maximum limit for the left subtree and mi = INT_MIN to check the minimum limit for the right subtree. 

  • Traverse from arr[1] to arr[n-1], n is the size of the array.
  • For each element of the array check 
  • If ( arr[j] > arr[j-1] && arr[j] > mi && arr[j] < ma ), update mi = arr[j-1] 

Else if ( arr[j] mi && arr[j] < ma ), update ma = arr[j] 

Break from the loop If none of the above two conditions are true. The element will not be inserted in the new level if conditions are not met.

C++ Code

//Find if the given array of size n can represent BST
//of n levels or not
#include <bits/stdc++.h>
using namespace std;


int main()
{
    int arr[] = { 5223, 3400, 883, 1211, 990 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int ma = INT_MAX;
    int mi = INT_MIN;
    bool f = true;

    for (int j = 1; j < n; j++) 
    {
        //if it is greater than the previous element and within the range
        // this element can be inserted to the right else left if in range
        
        if (arr[j] > arr[j - 1] && arr[j] > mi && arr[j] < ma) {
            // ma will remain the same, update mi
            mi = arr[j - 1];
        }
        
        else if (arr[j] < arr[j - 1] && arr[j] > mi && arr[j] < ma) {
            // mi will remain the same, update ma
            ma = arr[j - 1];
        }
        else {
            f = false;
            break;
        }
    }

    if (f) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }

    return 0;
}

 

Output: 

Yes

JAVA Code

//Find if the given array of size n can represent BST
//of n levels or not
class Find_if_the_given_array_of_size_n_can_represent_BST
{
    
    
    public static void main(String args[])
    {
        int arr[] = {5223, 3400, 883, 1211, 990};
        int n = arr.length;
        int ma = Integer.MAX_VALUE;
        int mi = Integer.MIN_VALUE;
        boolean f= true;
        
        
        for (int j = 1; j < n; j++) 
        {
             //if it is greater than the previous element and within the range
             // this element can be inserted to the right else left if in range
            if (arr[j] > arr[j - 1] && arr[j] > mi && arr[j] < ma) 
            {
                // ma will remain the same, update mi
                mi = arr[j - 1];
            }
            else if (arr[j] < arr[j - 1] && arr[j] > mi && arr[j] < ma) 
            {
                // mi will remain the same, update ma
                ma = arr[j - 1];
            }
            else 
            {
                f = false;
                break;
            }
        }
        
        
        if (f) {
            System.out.println("Yes");
        }
        else {
            System.out.println("No");
        }
    }
}

 

Output: 

Yes

Complexity Analysis

Time Complexity: O(N), Where N is the size of the array. It takes O(N) because we only traverse the array once and to traverse the array of size N it takes O(N) time.

Space Complexity: O(1), We do not use any extra space.

Check out this problem - Next Smaller Element

Frequently Asked Questions

What is a self balanced BST?

Self balanced BST (Binary Search Tree) is a special type of BST which automatically adjusts its height as small as possible whenever we do operations like deletion or insertion. 

For a BST to be self balanced, it must follow the rules of BST.

What rules must a binary tree follow to be called BST?

For a binary tree to be a BST, it must follow properties like: 

  1. For a node, all the nodes in the left subtree have values less than the value of the current node.
  2. For a node, all the nodes in the right subtree have values greater than the value of the current node.
  3. The left subtree and the right subtree should also be binary search trees and follow all three properties.

What is the most efficient way to find if the given array of size n can represent BST of n levels or not?

There are multiple ways to do this. The most efficient method is to set the max and min limit for each node and traverse the array and check.

Conclusion

In this blog, we learned the various methods to solve the very popular interview question to find if the given array of size n can represent BST of n levels or not. We learned in most logical sequences from brute force to the optimal solution. I hope you enjoyed reading our blog on ‘find if the given array of size n can represent BST of n levels or not.

Recommended problems -

 

Refer to our Guided Path on Coding Ninjas Studio to upskill ourselves in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning, and many more! But suppose we have just started our learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, we must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, we may consider our paid courses to give our career an edge over others!

Do upvote this blog if you find it helpful and engaging!

Happy Learning!!

Topics covered
1.
Introduction
1.1.
Problem Description
1.2.
Sample Examples
2.
Method 1: By Constructing Binary Search Tree
2.1.
Algorithm
2.2.
C++ code
2.3.
JAVA code
2.3.1.
Complexity Analysis
3.
Method 2: without constructing Binary Search Tree
3.1.
Algorithm
3.2.
C++ Code
3.3.
JAVA Code
3.3.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is a self balanced BST?
4.2.
What rules must a binary tree follow to be called BST?
4.3.
What is the most efficient way to find if the given array of size n can represent BST of n levels or not?
5.
Conclusion