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 |
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 <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 |
Output:
Yes
leave a comment
0 Comments