Start learning free

LESSON 331 OF 414 · BINARY TREES

Maximum Sum BST in Binary Tree in Scala: O(n) with Post-Order DFS

Practice O(n) Read the full explanation

Given a binary tree root, the task is to 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.

Example 4:

Input: root = [2,1,3]
Output: 6

Example 5:

Input: root = [5,4,8,3,null,6,3]
Output: 7

 

Constraints:

  • Each tree has at most 40000 nodes.
  • Each node's value is between [-4 * 10^4 , 4 * 10^4].
STEP 1 OF 19
    Ctrl + Enter to check

    SCALA · BINARY TREES

    Max Sum Bst in Scala, explained

    Problem overview

    The method maxSumBST receives the root of a binary tree and returns the largest sum of the values in any subtree that is a binary search tree (BST). In a BST, everything in a node's left subtree is strictly less than the node, everything in its right subtree is strictly greater, and both subtrees are BSTs. When every BST subtree has a negative sum, the answer is 0, meaning an empty BST.

    The tree with root 2 and children 1 and 3 is a BST with sum 6, so the answer is 6. The tree with root 4, left child 3 and 3's children 1 and 2 is not a BST at the top, since 2 is greater than 3. The subtree rooted at 3 isn't a BST either, and the best BST is the single node 2, so the answer is 2. The tree with root -4 and children -2 and -5 gives 0.

    Approach: one pass, each subtree reports four facts

    The straightforward solution tests every subtree separately, walking each one again to check the bounds, and that repeats a lot of work. This lesson visits every node once, bottom up, in post order: both children are finished before their parent.

    A node's subtree is a BST exactly when:

    • its left subtree is a BST;
    • its right subtree is a BST;
    • the node's value is greater than the maximum of the left subtree;
    • the node's value is less than the minimum of the right subtree.

    So each call returns four facts about its subtree: whether it is a BST, its minimum, its maximum and its sum. Given the facts of the two children, the parent decides in constant time, and computes its own facts. Whenever a subtree is a BST, its sum is compared with the best answer so far.

    An empty subtree is a BST with sum 0. Its minimum is set to the largest possible Int and its maximum to the smallest. Then, for a node with an empty child, the checks "value greater than left maximum" and "value less than right minimum" pass automatically, and the empty side never wins when the parent computes its own minimum and maximum.

    Step by step

    1. Declare the field result with var and the value 0. Scala infers Int.
    2. In maxSumBST, call dfs(root), ignore the array it returns, and end with result.
    3. Declare dfs with a TreeNode parameter and the result type Array[Int]. The four facts are packed into an array of four numbers: the BST flag as 1 or 0 (an Array[Int] can't hold a boolean), then the minimum, the maximum and the sum.
    4. Base case. For null, return Array(1, Int.MaxValue, Int.MinValue, 0).
    5. Read the left facts. Call dfs(root.left) and store the array in left. Then isLeftBST is left(0) == 1, and leftMin, leftMax and leftSum are entries 1, 2 and 3.
    6. Read the right facts the same way into right, isRightBST, rightMin, rightMax and rightSum.
    7. Start with the children's verdict. Declare var isRootBST as isLeftBST && isRightBST. It is a var because the next check may still turn it false.
    8. Compute the sum rootSum as root.value + leftSum + rightSum. It is needed even if the subtree is not a BST, as the parent will use it.
    9. Compute the minimum and the maximum of the subtree with nested math.min and math.max calls over the children's values and root.value.
    10. Apply the BST rule. If root.value <= leftMax || root.value >= rightMin, set isRootBST to false. The comparisons are non-strict because equal values break the rule.
    11. Update the answer. If isRootBST is still true, set result to math.max(result, rootSum).
    12. Return the four facts in the order the parent reads them: Array(if (isRootBST) 1 else 0, rootMin, rootMax, rootSum).

    The solution in Scala

    class Solution {
    var result = 0

    def dfs(root: TreeNode): Array[Int] = {
        if (root == null) {
            return Array(1, Int.MaxValue, Int.MinValue, 0)
        }
        val left = dfs(root.left)
        val isLeftBST = left(0) == 1
        val leftMin = left(1)
        val leftMax = left(2)
        val leftSum = left(3)

        val right = dfs(root.right)
        val isRightBST = right(0) == 1
        val rightMin = right(1)
        val rightMax = right(2)
        val rightSum = right(3)

        var isRootBST = isLeftBST && isRightBST
        val rootSum = root.value + leftSum + rightSum
        val rootMin = math.min(math.min(leftMin, rightMin), root.value)
        val rootMax = math.max(math.max(leftMax, rightMax), root.value)
        if (root.value <= leftMax || root.value >= rightMin) {
            isRootBST = false
        }
        if (isRootBST) {
            result = math.max(result, rootSum)
        }
        Array(if (isRootBST) 1 else 0, rootMin, rootMax, rootSum)
    }

    def maxSumBST(root: TreeNode): Int = {
        dfs(root)
        result
    }
}

    As an example, take the root 2 with the children 1 and 3. The leaf 1 gets the empty facts from both sides: Array(1, Int.MaxValue, Int.MinValue, 0). Its value is not less than or equal to the left maximum (the smallest Int), and not greater than or equal to the right minimum (the largest Int), so it is a BST and returns Array(1, 1, 1, 1). The leaf 3 returns Array(1, 3, 3, 3). At the root, 2 is greater than the left maximum 1 and less than the right minimum 3, so the whole tree is a BST with sum 6.

    Scala details:

    • An array as a tuple. Packing facts into an Array[Int] works because they are all numbers. The flag has to be 1 or 0. Scala could return a tuple or a small class with named fields instead, which would be more readable.
    • Array reads use parentheses: left(0), not left[0].
    • if as an expression inside Array(...) turns the flag back into a number, because Scala has no ternary operator.
    • Int.MaxValue and Int.MinValue are 2147483647 and -2147483648. They are used only as comparison bounds for empty sides. They are never added to anything, so there is no overflow. The node values here are far smaller.
    • math.min and math.max take two arguments, so three values need two nested calls.
    • The ignored result. dfs(root) on its own line is a statement whose value is discarded. The point is its effect on result.
    • The field persists. result belongs to the object. Calling maxSumBST twice on the same Solution object keeps the larger answer of the two calls.

    Complexity

    Time: O(n). Each node is visited once and does constant work, plus one constant-time call for each missing child.

    Space: O(h), where h is the height of the tree, for the recursion. Each call also allocates a four-element array that is dropped after its parent reads it. This is a clear improvement over testing each subtree from scratch, which can take cubic time in a chain-shaped tree.

    Edge cases and common mistakes

    • All values negative. The answer is 0, because result starts at 0. A root of -4 with children -2 and -5 gives 0.
    • A node with an empty side. The sentinels make the checks pass, so a leaf is a BST and a node with one child is checked only against that child's side.
    • Equal values. A root 2 with a single child 2 isn't a BST, so the answer is 2. The checks use <= and >= for exactly this reason.
    • Comparing with the direct children only. The root 10 with a left child 5 whose right child is 15 would pass a children-only check. Using the left subtree's maximum, which is 15, catches it. The best BST there is the subtree rooted at 5, with sum 20.
    • Reporting facts for a subtree that isn't a BST. Its minimum, maximum and sum are still real values. The flag in entry 0 is what tells the parent that this subtree is not a BST, and through isLeftBST and isRightBST that makes every ancestor fail as well.
    • Updating the answer only at the root. The best BST is usually deep inside the tree. The update happens in every call.

    Testing

    • Root 1 with left child 4 (children 2, 4) and right child 3 (children 2, 5 where 5 has the children 4, 6): 20.
    • Root 4 with left child 3 (children 1, 2): 2.
    • Root -4 with children -2 and -5: 0.
    • Root 2 with children 1 and 3: 6.
    • Root 5 with left child 4 (child 3) and right child 8 (children 6 and 3): 7.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free