Largest BST Subtree

Description

null

Solution(javascript)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
const largestBSTSubtree = function (root) {
  let max = 0

  const aux = (node) => {
    if (!node) {
      return [true, 0, null, null]
    }
    const [leftValid, leftCount, leftMin, leftMax] = aux(node.left)
    const [rightValid, rightCount, rightMin, rightMax] = aux(node.right)
    let currentValid = true
    if ((leftMax !== null && node.val <= leftMax) || (rightMin !== null && node.val >= rightMin)) {
      currentValid = false
    }
    currentValid = leftValid && rightValid && currentValid
    const currentMin = leftMin === null ? node.val : leftMin
    const currentMax = rightMax === null ? node.val : rightMax
    if (currentValid) {
      max = Math.max(
        max,
        leftCount + rightCount + 1,
      )
    }
    return [currentValid, leftCount + rightCount + 1, currentMin, currentMax]
  }
  aux(root)
  return max
}