Maximum Sum BST in Binary Tree LeetCode solution in JavaScript

1
var maxSumBST = function (root) {
2
  let max = 0;
3
  const dfs = (node) => {
4
    // NoNode
5
    if (!node) return [true, 0, Infinity, -Infinity];
6

7
    // LeafNode
8
    if (node && !node.left && !node.right) {
9
      max = Math.max(max, node.val);
10
      return [true, node.val, node.val, node.val];
11
    }
12

13
    const [isLeftValid, leftVal, leftMin, leftMax] = dfs(node.left);
14
    const [isRightValid, rightVal, rightMin, rightMax] = dfs(node.right);
15

16
    /**
17
     * To establish that the current node is also a valid BST, we need to verify the following:
18
     * 1. Left sub tree is a valid BST
19
     * 2. Right sub tree is a valid BST
20
     * 3. The values in the left BST are smaller than current node's value
21
     * 4. The values in the right BST are greater than current node's value
22
     **/
23
    if (
24
      isLeftValid &&
25
      isRightValid &&
26
      node.val > leftMax &&
27
      node.val < rightMin
28
    ) {
29
      max = Math.max(max, leftVal + rightVal + node.val);
30
      return [
31
        true,
32
        leftVal + rightVal + node.val,
33
        /**
34
         * 12
35
         * / \
36
         * 8 16
37
         * \ /
38
         * 9 15
39
         * \ /
40
         * 10 14
41
         * \ /
42
         * Infinity -Infinity
43
         * [Infinity and -Infinity are to depict NoNode cases]
44
         **/
45
        Math.min(node.val, leftMin),
46
        Math.max(node.val, rightMax),
47
      ];
48
    }
49

50
    return [false, 0, leftMax, rightMin];
51
  };
52
  dfs(root);
53

54
  return max;
55
};