1373. Maximum Sum BST in Binary Tree

Description

Given a binary tree root, return the maximum sum of all keys of any sub-tree which is also a Binary Search Tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

 

Example 1:

Input: root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
Output: 20
Explanation: Maximum sum in a valid Binary search tree is obtained in root node with key equal to 3.

Example 2:

Input: root = [4,3,null,1,2]
Output: 2
Explanation: Maximum sum in a valid Binary search tree is obtained in a single root node with key equal to 2.

Example 3:

Input: root = [-4,-2,-5]
Output: 0
Explanation: All values are negatives. Return an empty BST.

 

Constraints:

• The number of nodes in the tree is in the range [1, 4 * 104].
• -4 * 104 <= Node.val <= 4 * 104

 

Solutions

Solution: Depth-First Search

• Time complexity: O(n)
• Space complexity: O(h)

 

JavaScript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
const maxSumBST = function (root) {
  let result = 0;

  const traverse = node => {
    if (!node)
      return {
        isBTS: true,
        sum: 0,
        min: Number.MAX_SAFE_INTEGER,
        max: Number.MIN_SAFE_INTEGER,
      };
    const { val } = node;
    const left = traverse(node.left);
    const right = traverse(node.right);
    const isBTS = left.isBTS && right.isBTS && val > left.max && val < right.min;

    if (isBTS) {
      const sum = val + left.sum + right.sum;

      result = Math.max(sum, result);

      return {
        isBTS: true,
        sum,
        min: Math.min(val, left.min),
        max: Math.max(val, right.max),
      };
    }

    return {
      isBTS: false,
      sum: 0,
      min: Number.MAX_SAFE_INTEGER,
      max: Number.MIN_SAFE_INTEGER,
    };
  };

  traverse(root);

  return result;
};