Constant space O(nlogn) (worst case O(n^2)) recursive Java solution

  • 1
    public boolean verifyPreorder(int[] preorder) {
        return verifyPreorder(preorder, 0, preorder.length-1);
    private boolean verifyPreorder(int[] preorder, int l, int r) {
        if(l >= r-1) return true;
        int idx = l+1;
        while(idx <= r) {
            if(preorder[idx] > preorder[l])
        for(int i=idx; i<=r; i++) {
            if(preorder[i] < preorder[l]) return false;
        return verifyPreorder(preorder, l+1, idx-1) && verifyPreorder(preorder, idx, r);

    The idea is to find the left subtree and the right subtree and then call this function on each of them. If this is a balanced BST, the time complexity will be O(nlogn).

  • 0

    Constant space recursive it is self-contradict.

  • 0

    It is not tail recursion, the space is lgn.

Log in to reply

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