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.
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 <bits/stdc++.h> 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 |
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 <bits/stdc++.h> 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 |
Yes
leave a comment
0 Comments