#255 - Verify Preorder Sequence in Binary Search Tree

Medium • View on LeetCode • View on GitHub

Array Tree Binary Tree Stack Monotonic Stack Recursion Binary Search Tree

Problem Description

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

Solution

/**
 * @param {number[]} preorder
 * @return {boolean}
 */
var verifyPreorder = function(preorder) {
  let minLimit = -Infinity;
  const stack = [];

  for (const value of preorder) {
    while (stack.length && stack[stack.length - 1] < value) {
      minLimit = stack.pop();
    }
    if (value <= minLimit) return false;
    stack.push(value);
  }

  return true;
};