# 0255. Verify Preorder Sequence in Binary Search Tree

<https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree>

## Description

Given an array of **unique** integers `preorder`, return `true` *if it is the correct preorder traversal sequence of a binary search tree*.

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/03/12/preorder-tree.jpg)

```
**Input:** preorder = [5,2,1,3,6]
**Output:** true
```

**Example 2:**

```
**Input:** preorder = [5,2,6,1,3]
**Output:** false
```

**Constraints:**

* `1 <= preorder.length <= 104`
* `1 <= preorder[i] <= 104`
* All the elements of `preorder` are **unique**.

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

## ac1: stack, O(n) space

essential idea: right sub-tree always > parent node. very hard to come up with that.

```java
class Solution {
    public boolean verifyPreorder(int[] preorder) {
        // edge cases
        if (preorder.length < 2) return true;

        // walk
        Stack<Integer> stack = new Stack<Integer>();
        int parent = Integer.MIN_VALUE;
        for (int i = 0; i < preorder.length; i++) {
            if (preorder[i] <= parent) return false;

            while (stack.size() > 0 && preorder[i] > stack.peek()) {
                parent = stack.pop();
            }

            stack.push(preorder[i]);
        }

        // pass test, true
        return true;
    }
}
```

## ac2: utilize original array

Key point: using array like a stack.

```java
class Solution {
    public boolean verifyPreorder(int[] preorder) {
        // edge cases
        if (preorder.length < 2) return true;

        // walk
        int parent = Integer.MIN_VALUE;
        for (int i = 0, j = 0; i < preorder.length; i++) {
            if (preorder[i] <= parent) return false;

            while (j > 0 && preorder[i] > preorder[j-1]) {
                parent = preorder[--j];
            }

            preorder[j++] = preorder[i];
        }

        // pass test, true
        return true;
    }
}
```