LeetCode: Validate Binary Search Tree Solution

Approach (In-Order Traversal)

If the result of in-order traversal is a incremental array, then it is a binary search tree

Implementation

1var isValidBST = function (root) {
2  let inOrderTraversalOutput = []
3
4  const inOrderTraversal = node => {
5    if (!node) return
6
7    inOrderTraversal(node.left)
8    inOrderTraversalOutput.push(node.val)
9    inOrderTraversal(node.right)
10  }
11
12  inOrderTraversal(root)
13
14  for (let i = 1; i < inOrderTraversalOutput.length; i++) {
15    if (inOrderTraversalOutput[i - 1] >= inOrderTraversalOutput[i]) {
16      return false
17    }
18  }
19
20  return true
21}

Approach (Recursion)

Traverse the tree updated max, min of each half

Implementation

1var isValidBST = function (root) {
2  const recursion = (
3    node,
4    minLeft = Number.NEGATIVE_INFINITY,
5    maxRight = Number.POSITIVE_INFINITY
6  ) => {
7    if (!node) return true
8
9    const cond1 = minLeft < node.val && node.val < maxRight
10    const cond2 = recursion(node.left, minLeft, node.val)
11    const cond3 = recursion(node.right, node.val, maxRight)
12
13    return cond1 && cond2 && cond3
14  }
15
16  return recursion(root)
17}

References

Original problem