Verify Preorder Sequence in Binary Search Tree

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Follow up: Could you do it using only constant space complexity?


Recursive is not O(1) space

    public boolean verifyPreorder(int[] preorder) {
        return Helper(preorder, 0, preorder.length - 1);
    }

    private boolean Helper(int [] preorder, int b, int e){
        if(b >= e) return true;
        else{
            int root = preorder[b], i = b;
            for(; i <= e; i ++){
                if(preorder[i] > root)
                    break;
            }

            for(int j = i + 1; j <= e; j++)
                if(preorder[j] < root){
                    return false;
                }

            return Helper(preorder, b + 1, i - 1) && Helper(preorder, i, e);

        }

    }

results matching ""

    No results matching ""