# Check given array of size n can represent BST of n levels or not

Given an array of size n, the task is to find whether array can represent a BST with n levels.

Since levels are n, we construct a tree in the following manner.
Assuming a number X,

• Number higher than X is on the right side
• Number lower than X is on the left side.

Note: during the insertion, we never go beyond a number already visited.

Examples:

```Input : 500, 200, 90, 250, 100
Output : No

Input : 5123, 3300, 783, 1111, 890
Output : Yes
```

Explanation :

For the sequence 500, 200, 90, 250, 100 formed tree(in above image) can’t represent BST.

The sequence 5123, 3300, 783, 1111, 890 forms a binary search tree hence its a correct sequence.

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Method 1 : By constructing BST
We first insert all array values level by level in a Tree. To insert, we check if current value is less than previous value or greater. After constructing the tree, we check if the constructed tree is Binary Search Tree or not.

## C++

 `// C++ program to Check given array ` `// can represent BST or not ` `#include ` `using` `namespace` `std; ` ` `  `// structure for Binary Node ` `struct` `Node { ` `    ``int` `key; ` `    ``struct` `Node *right, *left; ` `}; ` ` `  `Node* newNode(``int` `num) ` `{ ` `    ``Node* temp = ``new` `Node; ` `    ``temp->key = num; ` `    ``temp->left = NULL; ` `    ``temp->right = NULL; ` `    ``return` `temp; ` `} ` ` `  `// To create a Tree with n levels. We always ` `// insert new node to left if it is less than ` `// previous value. ` `Node* createNLevelTree(``int` `arr[], ``int` `n) ` `{ ` `    ``Node* root = newNode(arr[0]); ` `    ``Node* temp = root; ` `    ``for` `(``int` `i = 1; i < n; i++) { ` `        ``if` `(temp->key > arr[i]) { ` `            ``temp->left = newNode(arr[i]); ` `            ``temp = temp->left; ` `        ``} ` `        ``else` `{ ` `            ``temp->right = newNode(arr[i]); ` `            ``temp = temp->right; ` `        ``} ` `    ``} ` `    ``return` `root; ` `} ` ` `  `// Please refer below post for details of this ` `// function. ` `// https:// www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/ ` `bool` `isBST(Node* root, ``int` `min, ``int` `max) ` `{ ` `    ``if` `(root == NULL) ` `        ``return` `true``; ` ` `  `    ``if` `(root->key < min || root->key > max) ` `        ``return` `false``; ` ` `  `    ``// Allow only distinct values ` `    ``return` `(isBST(root->left, min, ` `                  ``(root->key) - 1) ` `            ``&& isBST(root->right, ` `                     ``(root->key) + 1, max)); ` `} ` ` `  `// Returns tree if given array of size n can ` `// represent a BST of n levels. ` `bool` `canRepresentNLevelBST(``int` `arr[], ``int` `n) ` `{ ` `    ``Node* root = createNLevelTree(arr, n); ` `    ``return` `isBST(root, INT_MIN, INT_MAX); ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `arr[] = { 512, 330, 78, 11, 8 }; ` `    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr[0]); ` ` `  `    ``if` `(canRepresentNLevelBST(arr, n)) ` `        ``cout << ``"Yes"``; ` `    ``else` `        ``cout << ``"No"``; ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java program to Check given array ` `// can represent BST or not ` `class` `GFG  ` `{ ` ` `  `    ``// structure for Binary Node ` `    ``static` `class` `Node  ` `    ``{ ` `        ``int` `key; ` `        ``Node right, left; ` `    ``}; ` ` `  `    ``static` `Node newNode(``int` `num)  ` `    ``{ ` `        ``Node temp = ``new` `Node(); ` `        ``temp.key = num; ` `        ``temp.left = ``null``; ` `        ``temp.right = ``null``; ` `        ``return` `temp; ` `    ``} ` ` `  `    ``// To create a Tree with n levels. We always ` `    ``// insert new node to left if it is less than ` `    ``// previous value. ` `    ``static` `Node createNLevelTree(``int` `arr[], ``int` `n)  ` `    ``{ ` `        ``Node root = newNode(arr[``0``]); ` `        ``Node temp = root; ` `        ``for` `(``int` `i = ``1``; i < n; i++) ` `        ``{ ` `            ``if` `(temp.key > arr[i])  ` `            ``{ ` `                ``temp.left = newNode(arr[i]); ` `                ``temp = temp.left; ` `            ``}  ` `            ``else`  `            ``{ ` `                ``temp.right = newNode(arr[i]); ` `                ``temp = temp.right; ` `            ``} ` `        ``} ` `        ``return` `root; ` `    ``} ` ` `  `    ``// Please refer below post for details of this ` `    ``// function. ` `    ``// https:// www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/ ` `    ``static` `boolean` `isBST(Node root, ``int` `min, ``int` `max)  ` `    ``{ ` `        ``if` `(root == ``null``)  ` `        ``{ ` `            ``return` `true``; ` `        ``} ` ` `  `        ``if` `(root.key < min || root.key > max)  ` `        ``{ ` `            ``return` `false``; ` `        ``} ` ` `  `        ``// Allow only distinct values ` `        ``return` `(isBST(root.left, min, ` `                ``(root.key) - ``1``) ` `                ``&& isBST(root.right, ` `                        ``(root.key) + ``1``, max)); ` `    ``} ` ` `  `    ``// Returns tree if given array of size n can ` `    ``// represent a BST of n levels. ` `    ``static` `boolean` `canRepresentNLevelBST(``int` `arr[], ``int` `n)  ` `    ``{ ` `        ``Node root = createNLevelTree(arr, n); ` `        ``return` `isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE); ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String[] args)  ` `    ``{ ` `        ``int` `arr[] = {``512``, ``330``, ``78``, ``11``, ``8``}; ` `        ``int` `n = arr.length; ` ` `  `        ``if` `(canRepresentNLevelBST(arr, n))  ` `        ``{ ` `            ``System.out.println(``"Yes"``); ` `        ``}  ` `        ``else`  `        ``{ ` `            ``System.out.println(``"No"``); ` `        ``} ` `    ``} ` `} ` ` `  `/* This code contributed by PrinciRaj1992 */`

## C#

 `// C# program to Check given array ` `// can represent BST or not ` `using` `System; ` ` `  `class` `GFG  ` `{ ` ` `  `    ``// structure for Binary Node ` `    ``public` `class` `Node  ` `    ``{ ` `        ``public` `int` `key; ` `        ``public` `Node right, left; ` `    ``}; ` ` `  `    ``static` `Node newNode(``int` `num)  ` `    ``{ ` `        ``Node temp = ``new` `Node(); ` `        ``temp.key = num; ` `        ``temp.left = ``null``; ` `        ``temp.right = ``null``; ` `        ``return` `temp; ` `    ``} ` ` `  `    ``// To create a Tree with n levels. We always ` `    ``// insert new node to left if it is less than ` `    ``// previous value. ` `    ``static` `Node createNLevelTree(``int` `[]arr, ``int` `n)  ` `    ``{ ` `        ``Node root = newNode(arr[0]); ` `        ``Node temp = root; ` `        ``for` `(``int` `i = 1; i < n; i++) ` `        ``{ ` `            ``if` `(temp.key > arr[i])  ` `            ``{ ` `                ``temp.left = newNode(arr[i]); ` `                ``temp = temp.left; ` `            ``}  ` `            ``else` `            ``{ ` `                ``temp.right = newNode(arr[i]); ` `                ``temp = temp.right; ` `            ``} ` `        ``} ` `        ``return` `root; ` `    ``} ` ` `  `    ``// Please refer below post for details of this ` `    ``// function. ` `    ``// https:// www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/ ` `    ``static` `bool` `isBST(Node root, ``int` `min, ``int` `max)  ` `    ``{ ` `        ``if` `(root == ``null``)  ` `        ``{ ` `            ``return` `true``; ` `        ``} ` ` `  `        ``if` `(root.key < min || root.key > max)  ` `        ``{ ` `            ``return` `false``; ` `        ``} ` ` `  `        ``// Allow only distinct values ` `        ``return` `(isBST(root.left, min, ` `                ``(root.key) - 1) &&  ` `                ``isBST(root.right, ` `                ``(root.key) + 1, max)); ` `    ``} ` ` `  `    ``// Returns tree if given array of size n can ` `    ``// represent a BST of n levels. ` `    ``static` `bool` `canRepresentNLevelBST(``int` `[]arr, ``int` `n)  ` `    ``{ ` `        ``Node root = createNLevelTree(arr, n); ` `        ``return` `isBST(root, ``int``.MinValue, ``int``.MaxValue); ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main(String[] args)  ` `    ``{ ` `        ``int` `[]arr = {512, 330, 78, 11, 8}; ` `        ``int` `n = arr.Length; ` ` `  `        ``if` `(canRepresentNLevelBST(arr, n))  ` `        ``{ ` `            ``Console.WriteLine(``"Yes"``); ` `        ``}  ` `        ``else` `        ``{ ` `            ``Console.WriteLine(``"No"``); ` `        ``} ` `    ``} ` `} ` ` `  `// This code contributed by Rajput-Ji `

Output:

```Yes
```

Method 2 (Array Based)
1. Take two variables max = INT_MAX to mark the maximum limit for left subtree and min = INT_MIN to mark the minimum limit for right subtree.
2. Loop from arr[1] to arr[n-1]
3. for each element check
a. If ( arr[i] > arr[i-1] && arr[i] > min && arr[i] < max ), update min = arr[i-1]
b. Else if ( arr[i] min && arr[i] < max ), update max = arr[i]
c. If none of the above two conditions hold, then element will not be inserted in a new level, so break.

## C++

 `// C++ program to Check given array ` `// can represent BST or not ` `#include ` `using` `namespace` `std; ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `arr[] = { 5123, 3300, 783, 1111, 890 }; ` `    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr[0]); ` `    ``int` `max = INT_MAX; ` `    ``int` `min = INT_MIN; ` `    ``bool` `flag = ``true``; ` ` `  `    ``for` `(``int` `i = 1; i < n; i++) { ` ` `  `        ``// This element can be inserted to the right ` `        ``// of the previous element, only if it is greater ` `        ``// than the previous element and in the range. ` `        ``if` `(arr[i] > arr[i - 1] && arr[i] > min && arr[i] < max) { ` `            ``// max remains same, update min ` `            ``min = arr[i - 1]; ` `        ``} ` `        ``// This element can be inserted to the left ` `        ``// of the previous element, only if it is lesser ` `        ``// than the previous element and in the range. ` `        ``else` `if` `(arr[i] < arr[i - 1] && arr[i] > min && arr[i] < max) { ` `            ``// min remains same, update max ` `            ``max = arr[i - 1]; ` `        ``} ` `        ``else` `{ ` `            ``flag = ``false``; ` `            ``break``; ` `        ``} ` `    ``} ` ` `  `    ``if` `(flag) { ` `        ``cout << ``"Yes"``; ` `    ``} ` `    ``else` `{ ` `        ``// if the loop completed successfully without encountering else condition ` `        ``cout << ``"No"``; ` `    ``} ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java program to Check given array  ` `// can represent BST or not  ` `class` `Solution ` `{ ` `   `  `// Driver code  ` `public` `static` `void` `main(String args[])  ` `{  ` `    ``int` `arr[] = { ``5123``, ``3300``, ``783``, ``1111``, ``890` `};  ` `    ``int` `n = arr.length;  ` `    ``int` `max = Integer.MAX_VALUE;  ` `    ``int` `min = Integer.MIN_VALUE;  ` `    ``boolean` `flag = ``true``;  ` `   `  `    ``for` `(``int` `i = ``1``; i < n; i++) {  ` `   `  `        ``// This element can be inserted to the right  ` `        ``// of the previous element, only if it is greater  ` `        ``// than the previous element and in the range.  ` `        ``if` `(arr[i] > arr[i - ``1``] && arr[i] > min && arr[i] < max) {  ` `            ``// max remains same, update min  ` `            ``min = arr[i - ``1``];  ` `        ``}  ` `        ``// This element can be inserted to the left  ` `        ``// of the previous element, only if it is lesser  ` `        ``// than the previous element and in the range.  ` `        ``else` `if` `(arr[i] < arr[i - ``1``] && arr[i] > min && arr[i] < max) {  ` `            ``// min remains same, update max  ` `            ``max = arr[i - ``1``];  ` `        ``}  ` `        ``else` `{  ` `            ``flag = ``false``;  ` `            ``break``;  ` `        ``}  ` `    ``}  ` `   `  `    ``if` `(flag) {  ` `        ``System.out.println(``"Yes"``);  ` `    ``}  ` `    ``else` `{  ` `        ``// if the loop completed successfully without encountering else condition  ` `        ``System.out.println(``"No"``);  ` `    ``}  ` `   `  `}  ` `} ` `//contributed by Arnab Kundu `

## Python3

 `# Python3 program to Check given array  ` `# can represent BST or not ` ` `  `# Driver Code  ` `if` `__name__ ``=``=` `'__main__'``: ` `    ``arr ``=` `[``5123``, ``3300``, ``783``, ``1111``, ``890``]  ` `    ``n ``=` `len``(arr) ` `    ``max` `=` `2147483647` `# INT_MAX  ` `    ``min` `=` `-``2147483648` `# INT_MIN  ` `    ``flag ``=` `True` ` `  `    ``for` `i ``in` `range``(``1``,n):  ` ` `  `        ``# This element can be inserted to the  ` `        ``# right of the previous element, only  ` `        ``# if it is greater than the previous ` `        ``# element and in the range.  ` `        ``if` `(arr[i] > arr[i ``-` `1``] ``and` `            ``arr[i] > ``min` `and` `arr[i] < ``max``):  ` `                 `  `            ``# max remains same, update min  ` `            ``min` `=` `arr[i ``-` `1``]  ` `         `  `        ``# This element can be inserted to the  ` `        ``# left of the previous element, only  ` `        ``# if it is lesser than the previous  ` `        ``# element and in the range.  ` `        ``elif` `(arr[i] < arr[i ``-` `1``] ``and`  `              ``arr[i] > ``min` `and` `arr[i] < ``max``):  ` `                   `  `            ``# min remains same, update max  ` `            ``max` `=` `arr[i ``-` `1``]  ` `         `  `        ``else` `:  ` `            ``flag ``=` `False` `            ``break` `         `  `    ``if` `(flag):  ` `        ``print``(``"Yes"``) ` `     `  `    ``else``:  ` `         `  `        ``# if the loop completed successfully  ` `        ``# without encountering else condition  ` `        ``print``(``"No"``)  ` `     `  `# This code is contributed  ` `# by SHUBHAMSINGH10 `

## C#

 `using` `System; ` ` `  `// C#  program to Check given array   ` `// can represent BST or not   ` `public` `class` `Solution ` `{ ` ` `  `// Driver code   ` `public` `static` `void` `Main(``string``[] args) ` `{ ` `    ``int``[] arr = ``new` `int``[] {5123, 3300, 783, 1111, 890}; ` `    ``int` `n = arr.Length; ` `    ``int` `max = ``int``.MaxValue; ` `    ``int` `min = ``int``.MinValue; ` `    ``bool` `flag = ``true``; ` ` `  `    ``for` `(``int` `i = 1; i < n; i++) ` `    ``{ ` ` `  `        ``// This element can be inserted to the right   ` `        ``// of the previous element, only if it is greater   ` `        ``// than the previous element and in the range.   ` `        ``if` `(arr[i] > arr[i - 1] && arr[i] > min && arr[i] < max) ` `        ``{ ` `            ``// max remains same, update min   ` `            ``min = arr[i - 1]; ` `        ``} ` `        ``// This element can be inserted to the left   ` `        ``// of the previous element, only if it is lesser   ` `        ``// than the previous element and in the range.   ` `        ``else` `if` `(arr[i] < arr[i - 1] && arr[i] > min && arr[i] < max) ` `        ``{ ` `            ``// min remains same, update max   ` `            ``max = arr[i - 1]; ` `        ``} ` `        ``else` `        ``{ ` `            ``flag = ``false``; ` `            ``break``; ` `        ``} ` `    ``} ` ` `  `    ``if` `(flag) ` `    ``{ ` `        ``Console.WriteLine(``"Yes"``); ` `    ``} ` `    ``else` `    ``{ ` `        ``// if the loop completed successfully without encountering else condition   ` `        ``Console.WriteLine(``"No"``); ` `    ``} ` ` `  `} ` `} ` ` `  ` ``//  This code is contributed by Shrikant13 `

Output:

```Yes
```