# Divide Conquer Java Solution

• A BST's left child is always < root and right child is always > root.

``````public boolean verifyPreorder(int[] preorder) {
if(preorder == null || preorder.length == 0) return true;
return verify(preorder, 0, preorder.length - 1);
}

private boolean verify(int[] a, int start, int end) {
if(start >= end) return true;
int pivot = a[start];
int bigger = -1;
for(int i = start + 1; i <= end; i++) {
if(bigger == -1 && a[i] > pivot) bigger = i;
if(bigger != -1 && a[i] < pivot) return false;
}
if(bigger == -1) {
return verify(a, start + 1, end);
} else {
return verify(a, start + 1, bigger - 1) && verify(a, bigger, end);
}
}``````

• Hi. qianzhige. Thanks for your sharing. Well, I think it is the most easy and simple idea. However, translating it into C++ gives the TLE...

``````class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
int n = preorder.size();
return verify(preorder, 0, n - 1);
}
private:
bool verify(vector<int>& preorder, int l, int r) {
if (l >= r) return true;
int pivot = preorder[l], m = -1;
for (int i = l + 1; i <= r; i++) {
if (m == -1 && preorder[i] > pivot) m = i;
if (m != -1 && preorder[i] < pivot) return false;
}
if (m == -1) return verify(preorder, l + 1, r);
return verify(preorder, l + 1, m - 1) && verify(preorder, m, r);
}
};
``````

Even I use `int*` instead of `vector<int>`, TLE still occurs...

``````class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
int n = preorder.size();
int* p = new int[n];
for (int i = 0; i < n; i++) p[i] = preorder[i];
return verify(p, 0, n - 1);
}
private:
bool verify(int* p, int l, int r) {
if (l >= r) return true;
int pivot = p[l], m = -1;
for (int i = l + 1; i <= r; i++) {
if (m == -1 && p[i] > pivot) m = i;
if (m != -1 && p[i] < pivot) return false;
}
if (m == -1) return verify(p, l + 1, r);
return verify(p, l + 1, m - 1) && verify(p, m, r);
}
};``````

• The time complexity for this solution is O(n^2)

• my approach is similar. it passed, but almost TLE.

class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
return verify(preorder, 0, preorder.size()-1, INT_MIN, INT_MAX);
}

``````bool verify(vector<int>& preorder, int s, int e, int min, int max) {
if (s > e) return true;
int r = preorder[s];
if (!(r >= min && r <= max)) return false;
if (s==e) return true;
//pre-cond s<e
int p;
for (p=s+1; p<=e && preorder[p] < r; ++p);

if (verify(preorder, s+1, p-1, min, r) && verify(preorder, p, e, r, max))
return true;
return false;
}
``````

};

• @qianzhige it looks like that this solution is `O(nlogn)` because `T(n) = 2T(n/2) + n`.

• @dachuan.huang +1. But the worst case will be O(N^2) when the tree looks like a descending single chain.

• nice solution, same here and I believe the performance is O(NlogN) - each node is considered logN times, but I'm bit unclear on this, any thoughts. Thanks!

``````    public bool VerifyPreorder(int[] preorder)
{
return IsPreOrder(preorder, 0, preorder.Length - 1, 0, 0, false, false);
}

public bool IsPreOrder(int[] arr, int left, int right, int min, int max, bool applyMin, bool applyMax)
{
if (left > right) return true;

int root = arr[left];
if ((applyMin && root < min) || (applyMax && root > max)) return false;

int pos = left + 1;
while (pos <= right && arr[pos] < root) pos++;

return IsPreOrder(arr, left + 1, pos - 1, min, root, applyMin, true)
&& IsPreOrder(arr, pos, right, root, max, true, applyMax);
}
``````

• Apart from stack of recursion, what is the space complexity here? I think it is average O(logn) and worst O(n). Since each recursion function's pivot and bigger will be kept until all sub-function are done. Correct me if I'm wrong.

• Same idea. Slow too. Have fun with it. lol

``````class Solution {
public boolean verifyPreorder(int[] preorder) {
return helper(preorder, 0, preorder.length - 1);
}
public boolean helper(int[] preorder, int start, int end) {
if (start >= end) {
return true;
}
int root = preorder[start];
int i = start + 1;
while (i <= end){
if (preorder[i] > root) {
break;
}
i++;
}
if (!valid(preorder, root, i, end)) {
return false;
}
return helper(preorder, start + 1, i - 1) && helper(preorder, i, end);
}
public boolean valid(int[] preorder, int root, int start, int end) {
if (start > end) {
return true;
}
for (int i = start; i <= end; i++) {
if (preorder[i] < root) {
return false;
}
}
return true;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.