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


  • 1
    J
    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])
                break;
            idx++;
        }
        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
    W

    Constant space recursive solution....lol it is self-contradict.


  • 0
    H

    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.