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

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:

Input 2: 

5223, 3400, 883, 1211, 990

Output: 

Yes

Explanation:

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.