Skip to content

255. Verify Preorder Sequence in Binary Search Tree 👍

Approach 1: Backtracking

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  bool verifyPreorder(vector<int>& preorder) {
    int i = 0;
    dfs(preorder, i, INT_MIN, INT_MAX);
    return i == preorder.size();
  }

 private:
  void dfs(const vector<int>& preorder, int& i, int min, int max) {
    if (i == preorder.size())
      return;
    if (preorder[i] < min || preorder[i] > max)
      return;

    const int val = preorder[i++];
    dfs(preorder, i, min, val);
    dfs(preorder, i, val, max);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public boolean verifyPreorder(int[] preorder) {
    dfs(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
    return i == preorder.length;
  }

  private int i = 0;

  private void dfs(int[] preorder, int mn, int mx) {
    if (i == preorder.length)
      return;
    if (preorder[i] < mn || preorder[i] > mx)
      return;

    final int val = preorder[i++];
    dfs(preorder, mn, val);
    dfs(preorder, val, mx);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def verifyPreorder(self, preorder: list[int]) -> bool:
    i = 0

    def dfs(min: int, max: int) -> None:
      nonlocal i
      if i == len(preorder):
        return
      if preorder[i] < min or preorder[i] > max:
        return

      val = preorder[i]
      i += 1
      dfs(min, val)
      dfs(val, max)

    dfs(-math.inf, math.inf)
    return i == len(preorder)

Approach 2: Stack

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  bool verifyPreorder(vector<int>& preorder) {
    int low = INT_MIN;
    stack<int> stack;

    for (const int p : preorder) {
      if (p < low)
        return false;
      while (!stack.empty() && stack.top() < p)
        low = stack.top(), stack.pop();
      stack.push(p);
    }

    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public boolean verifyPreorder(int[] preorder) {
    int low = Integer.MIN_VALUE;
    Deque<Integer> stack = new ArrayDeque<>();

    for (final int p : preorder) {
      if (p < low)
        return false;
      while (!stack.isEmpty() && stack.peek() < p)
        low = stack.pop();
      stack.push(p);
    }

    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def verifyPreorder(self, preorder: list[int]) -> list[int]:
    low = -math.inf
    stack = []

    for p in preorder:
      if p < low:
        return False
      while stack and stack[-1] < p:
        low = stack.pop()
      stack.append(p)

    return True

Approach 3: Abuse original array

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  bool verifyPreorder(vector<int>& preorder) {
    int low = INT_MIN;
    int i = -1;

    for (const int p : preorder) {
      if (p < low)
        return false;
      while (i >= 0 && preorder[i] < p)
        low = preorder[i--];
      preorder[++i] = p;
    }

    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public boolean verifyPreorder(int[] preorder) {
    int low = Integer.MIN_VALUE;
    int i = -1;

    for (final int p : preorder) {
      if (p < low)
        return false;
      while (i >= 0 && preorder[i] < p)
        low = preorder[i--];
      preorder[++i] = p;
    }

    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def verifyPreorder(self, preorder: list[int]) -> bool:
    low = -math.inf
    i = -1

    for p in preorder:
      if p < low:
        return False
      while i >= 0 and preorder[i] < p:
        low = preorder[i]
        i -= 1
      i += 1
      preorder[i] = p

    return True