JS BFS solution returning early


  • 0
    Y

    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 = [{
        treeNode,
        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.