52ms, C++, O(1) space, O(n) time, Commented code


  • 0
    E

    Idea: Keep a max and min. Once you see a max. then update your min to existing max and max to new max. Any value at any time should be between min and max.

    Main problem here is finding the minimum (assuming there can be negative numbers).

    Assume first element is the minimum. Then go through the array till we see first non-decreasing element.
    That's the min we will use.

    
    class Solution {
    public:
        bool verifyPreorder(vector<int>& preorder) {
            if(preorder.size()==0) return true;
            int maxVal = preorder[0];
            int minVal = preorder[0];
            // go through the till you find the an element which is greater than previous
            // Example: 3,2,1,4 . In this case that element is 4. So we stop at 4
            our minima is 1
            for ( int i=0; i < preorder.size(); i++ ) {
                if(i > 0 && preorder[i] > preorder[i-1]) break;
                minVal = min(minVal, preorder[i]);
            }
           //
           // Go through the array second time
            for ( int i=0; i < preorder.size(); i++ ) {
                if ( preorder[i] < minVal) {
                    // If current value is less than min.. this is not possible
                    return false;
                }
                if ( preorder[i] > maxVal ) {
                    minVal = maxVal;
                    maxVal = preorder[i];
                }
            }
            return true;
        }
    };
    

  • 0
    M

    Find a Corner case: [10,5,1,7,4,20,15]


  • 0
    E

    in this case root is 10
    where does 4 fit?


  • 0
    K

    It fails at [6,3,1,5,2]

    It seems like when going rightward, you lost the track of which parent node the right chain is attached to.


  • -1
    E

    [6,3,1,5,2] is an invalid input.
    this input means: 6 has two children: 3(left child) and 1(right child).
    and 3 has two children: 5(left child) and 2(right child).

    this is not a valid input because 6 cannot have a leftchild of 3 and a right child of 1.
    3 cannot have 5 as a left child


  • 0
    X

    Best solution I saw so far, but still confusing about the idea. Can you elaborate more details of the algorithm? It is very appreciated if an example can be given.


  • 0
    S

    It failed with the case: [10,7,4,8,6,40,23]. It's a bad sequence, but it returned true with your code. This might be a new test case.


  • 0
    V

    It could be a valid input . [3,1,5,2] are all left children of 6 . BST in serialized format : { 6 ,3,#,1,5,#,#,2}


  • 0
    X

    { 6 ,3,#,1,5,#,#,2} is not a valid BST. Coz, 2 is left child of 5, however, 2 is on the right subtree of 3.


  • 0

    @ediston said in 52ms, C++, O(1) space, O(n) time, Commented code:

    [6,3,1,5,2]

    there is no so-called "invalid input". Every input is valid, it is your code's responsibility to check whether the input is a preorder of a BST.

    If the tree is not BST, you should output "false", however, your code outputs "true" the test case [6,3,1,5,2], which is definitely not a preorder of any BST


Log in to reply
 

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