JS BFS solution returning early

  • 0

    This is better than the recursive approach that recurses down left subtrees first, since catches failures closer to the root.

    function isValidBST(treeNode) {
      if (!treeNode) {
        return true
      const q = [{
        upperBound: Number.POSITIVE_INFINITY,
        lowerBound: Number.NEGATIVE_INFINITY,
      while (q.length) {
        const {treeNode: {left, right, val}, upperBound, lowerBound} = q.shift()
        if (val >= upperBound || val <= lowerBound) {
          return false
        const nextLowerBound = Math.max(val, lowerBound)
        const nextUpperBound = Math.min(val, upperBound)
        if (left) {
          q.push({treeNode: left, lowerBound, upperBound: nextUpperBound})
        if (right) {
          q.push({treeNode: right, lowerBound: nextLowerBound, upperBound})
      return true

Log in to reply

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