Validating a Predefined BST Bypass

Question

I wrote code to test out of order traversal if it is a valid BST. for example, pre-order 1,2,4,3,5 is valid BST and 1,3,4,2 not

I built a whole tree from this pre-order sequence and then checked if this tree is a valid BST. These are O(N) solutions for the complexity of space and time.

Does anyone have a good approach? I have an intuition that we can do this in O (1) extra space.

Answer 1

Checking whether the permutation 1..n is a pre-order of a valid BST (that the BST, if it exists, is unique; imreal the answer is not a counterexample because the second reconstruction is not sorted) is equivalent to checking if the permutation is sorted by glass, i.e. avoids the 231-pattern. It seems that I can’t find any linear algorithm with constant space under any of these names, which, as a rule, suggests, given the attention that this problem attracted, that no one knows about a permanent additional space solution.

If you are ready to accept a read / write input that can be destroyed, then there is a linear time algorithm that uses constant extra space. There is no need to reconstruct the tree separately and then test it. Here are some of Python with this.

 def isbstpreorder(iterable): lowerbound = None stack = [] for x in iterable: if lowerbound is not None and x < lowerbound: return False while stack and stack[-1] < x: lowerbound = stack.pop() stack.append(x) return True 

To exclude separate storage for the stack, save it in the input list prefix.

Answer 2

The idea is to check if the input array can be divided into two submatrices representing the left and right subtrees. Obviously, this needs to be done recursively.

Here is some validated Java code to illustrate the same thing:

 import java.util.ArrayList; import java.util.List; public class PreOrderBSTCheck { /** * @param args */ public static void main(String[] args) { String ipStr = "1 4 2 3"; String[] ipArr = ipStr.split(" "); int[] intArr = new int[ipArr.length]; List<Integer> listArr = new ArrayList<Integer>(); for(int i = 0 ; i < ipArr.length ; i++) { intArr[i] = Integer.parseInt(ipArr[i]); listArr.add(intArr[i]); } //System.out.println("List size: "+listArr.size()); if(checkTree(listArr)) System.out.println("Valid"); else System.out.println("Invalid"); } public static boolean checkTree(List<Integer> arr) { if(arr.size() == 1) { return true; } List<Integer> left = new ArrayList<Integer>(); List<Integer> right = new ArrayList<Integer>(); Integer root = arr.get(0); int idx = 1; //adding left subtree nodes while(arr.get(idx) < root) { left.add(arr.get(idx++)); if(idx >= arr.size()) break; } //adding right subtree nodes if(! (idx >= arr.size())) while(arr.get(idx) > root) { right.add(arr.get(idx++)); if(idx >= arr.size()) break; } if(left.size() + right.size() == arr.size() - 1) { if(left.size()==0) { return true && checkTree(right); } else if(right.size() == 0) { return true && checkTree(left); } else { return checkTree(left) && checkTree(right); } } else { return false; } } } 

Answer 3

It is not possible to unambiguously construct a binary tree from a pre-order traversal, so it is impossible to verify whether it is a BST.

For example, 4, 2, 3, 6, 5 can do:

  4 / \ 2 6 \ / 3 5 

which is a BST as well:

 4 \ 2 \ 3 \ 6 \ 5 

which is not.

Answer 4

 int lower=-1; for(long int i=0;i<size;i++) { if(lower>-1 && pre[i] < lower) { lower=-2; break; } while(!isempty(s) && top(s)<pre[i]) { lower =top(s); pop(s); } push(s,pre[i]); } if(lower==-2) { cout<<"Invalid"<<endl; } else { cout<<"Valid BST"<<endl; } 

This algorithm will work for any sorted input, not just 1 to n. And O (1) additional space is required, i.e. Only the "lower" variable. If you try to solve this problem using a pen and paper, you will have to keep track of the variable, the one for which you are checking that the new value should not be less than this value. The lower one acts like a marker for which you check that the new value is not lower than the "lower" one. And you keep updating “lower” as soon as you get a higher value.

Answer 5

This can be done in O (n) time and O (n) complexity of the auxiliary space (for the recursion stack). The root node of the entire tree will have index 0 in the preorder array. In preorder, each node follows a set of elements of the left subtree, and then a set of elements of the right subtree. For each node, the correct subtree will be rooted in the next higher value of the array from this node. So, the main idea is to recursively split an array of pre-orders into left and right subtrees with a valid range of node values.

 public class IsBstPossibleFromPreorder { public static void main(String args[]){ int[] preorder = {40, 30, 35, 20, 80};//{6,3,0,5,4,8,7,9};//{3,2,5,1,7}; System.out.println(isBstPossible(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE, 0, preorder.length-1)); } /* li is root of current subtree ri is the index of the last element in the current subtree min, max range for the elements of current subtree */ private static boolean isBstPossible(int[] preorder, int min, int max, int li, int ri){ if (li==ri && preorder[li]>min && preorder[li]<max){ // if single node subtree... return true; } if (preorder[li]<=min || preorder[li]>=max ){ // if node value out of range return false; } int lsi = preorder[li+1]<preorder[li]?li+1:-1; // left subtree root index (-1 if no left subtree exits for node li) int rsi = findNextHigherElementIndex(preorder, li, ri); // right subtree root index (-1 if no right subtree exists for node li) boolean isLeftValid = (lsi==-1 || isBstPossible(preorder, min, preorder[li], lsi, rsi-1>lsi?rsi-1:lsi)); boolean isRightValid = (rsi==-1 || isBstPossible(preorder, preorder[li], max, rsi, ri)); return isLeftValid && isRightValid; } private static int findNextHigherElementIndex(int[] preorder, int li, int ri){ int x = -1; // -1 if no higher element on right side of li for (int i = li+1; i <= ri ; i++) { if (preorder[i]>preorder[li]){ x = i; break; } } return x; } } 

Answer 6

The first thing we can consider here is that for a pre-order traversal array, if at any point on the right side of the array we find a larger element than the current element, and if any element after that is a smaller element, we must consider that BST is impossible from that circumvention of the order.

for example: arr [] = {40,30,35,20,80,100} it is impossible to build a valid BST.

Explanation:

Here, when we start building a tree, 40 becomes the root of BST. Now, when we go 30, it goes in the left subtree, and now we find the next larger value 30, which is 35, as we know, for any lower or smaller element located in the left subtree 30, there should be from 30 to the next larger one, i.e. 35 Here. Thus, as we move forward, we find 20 that cannot fit to the left of 30, like after the next larger element, and, of course, not like child 35, since it will violate the BST property (i.e., any element of the right element subtree should be of great value always compared to the root). Therefore, a valid BST cannot be performed.

Now, to solve this problem, we can use the stack when we use it to find the next larger element in the Code array for the next larger element . Here we just need to make sure that there will not be less after the next larger element than after.

In the code, we initially accept root as the minimum possible value of INT_MIN. If the root is less than the current element at any time, we return false. Although the current item is larger than the item at the top of the stack, we expose it and set the root as a pop-up item. And we push the current item onto the stack for further comparison.

 bool check(int *arr, int n) { stack<int> s; int root=INT_MIN; for(int i=0;i<n;++i) { if(arr[i]<root) return false; while(!s.empty() && arr[i]>s.top()) { root=s.top(); s.pop(); } s.push(arr[i]); } return true; }