Start learning free

LESSON 307 OF 348 · BINARY TREES

Maximum Sum BST in Kotlin: O(n) with Min, Max and Sum per Subtree

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 13
    Ctrl + Enter to check

    KOTLIN · BINARY TREES

    Max Sum Bst in Kotlin, explained

    Problem overview

    The function maxSumBST receives the root of a binary tree, a TreeNode?, and returns the largest sum of keys over all subtrees that are binary search trees (BSTs). A subtree is a BST when its left side holds only smaller keys, its right side holds only larger keys, and both sides are BSTs. The empty tree is allowed and has the sum 0, so when every non-empty BST has a negative sum, as in [-4, -2, -5], the answer is 0. The tree has at most 40,000 nodes with values from -40,000 to 40,000.

    For [4, 3, null, 1, 2] the node 4 has a left child 3, whose children are 1 and 2. The node 3 breaks the rule because its right child 2 is smaller than it. So 3 and 4 cannot be roots of BSTs, and the best BST is the single node 2, with sum 2.

    Approach: one post-order pass that reports four facts

    The straightforward solution checks every subtree from scratch by scanning it, which repeats a lot of work. The faster idea is to let each subtree report what its parent needs to know, so that the parent decides in constant time. For a subtree, four facts are enough:

    1. whether it is a BST;
    2. its smallest key;
    3. its largest key;
    4. the sum of its keys.

    A node with value v is the root of a BST when both child subtrees are BSTs, v is greater than the largest key on the left, and v is smaller than the smallest key on the right. The facts for the node itself follow from the children: the minimum is the smallest of the two child minimums and v, the maximum is the largest of the two child maximums and v, and the sum is v plus both child sums.

    The children must be processed before the node, which makes this a post-order recursion. Whenever a node turns out to be the root of a BST, its sum is a candidate for the answer.

    An empty subtree needs facts that never get in the way. It is a BST, its sum is 0, and its minimum is the largest possible Int and its maximum is the smallest. Then a parent's checks v <= leftMax and v >= rightMin are false for an empty side, and the empty side never wins when taking the minimum or maximum.

    The example [4, 3, null, 1, 2] runs like this, listing the facts as (BST?, min, max, sum):

    node 1: leaf             (yes, 1, 1, 1)    result becomes 1
node 2: leaf             (yes, 2, 2, 2)    result becomes 2
node 3: left 1, right 2  3 >= right min 2, so not a BST:  (no, 1, 3, 6)
node 4: left is node 3   left is not a BST, so not a BST:  (no, 1, 4, 10)

    The answer is result, which is 2.

    Step by step

    1. Keep the best answer in a property result declared with var and set to 0. This also covers the empty-BST case.
    2. Call dfs from maxSumBST and return result. Only the side effect on result matters, so the array that dfs returns for the whole tree is ignored.
    3. Declare dfs so that it returns an IntArray of four entries. An int array can't hold a boolean, so the BST flag is stored as 1 or 0.
    4. Return the facts of the empty tree for a null node: 1, Int.MAX_VALUE, Int.MIN_VALUE and 0.
    5. Unpack the left result into isLeftBST (the flag equals 1), leftMin, leftMax and leftSum.
    6. Unpack the right result the same way.
    7. Start with isRootBST as a var that is true when both sides are BSTs. A later check may still turn it off.
    8. Compute rootSum: this node's value plus both sums. It is needed even when the node is not a BST, because the parent receives it.
    9. Compute rootMin from the left minimum, the right minimum and the node's value.
    10. Compute rootMax from the left maximum, the right maximum and the node's value.
    11. Check the node against its sides. If the value is less than or equal to leftMax, or greater than or equal to rightMin, the BST rule fails and isRootBST becomes false. The comparison is strict, so equal keys fail too.
    12. Update the answer. If the node is still a BST root, set result to the larger of result and rootSum.
    13. Return the four facts in the order the caller reads them: flag, minimum, maximum and sum.

    The solution in Kotlin

    class Solution {
    var result = 0

    fun dfs(root: TreeNode?): IntArray {
        if (root == null) {
            return intArrayOf(1, Int.MAX_VALUE, Int.MIN_VALUE, 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 = minOf(minOf(leftMin, rightMin), root.value)
        val rootMax = maxOf(maxOf(leftMax, rightMax), root.value)
        if (root.value <= leftMax || root.value >= rightMin) {
            isRootBST = false
        }
        if (isRootBST) {
            result = maxOf(result, rootSum)
        }
        return intArrayOf(if (isRootBST) 1 else 0, rootMin, rootMax, rootSum)
    }

    fun maxSumBST(root: TreeNode?): Int {
        dfs(root)
        return result
    }
}

    The Kotlin details worth knowing:

    • Type inference on the property. var result = 0 gets the type Int from its initial value, so no annotation is needed. As a property of the class, it keeps its value between calls on the same object, which means a second call to maxSumBST on one Solution would start from the previous answer.
    • An IntArray of mixed facts. intArrayOf(...) builds a primitive int array that is read by index. The comparison left[0] == 1 turns the stored flag back into a Boolean. The order of the entries is a convention that both sides of the call must share.
    • Int.MAX_VALUE and Int.MIN_VALUE are the largest and smallest Int, 2147483647 and -2147483648. They act as sentinels here. The problem's keys stay between -40,000 and 40,000, so no real key can collide with them.
    • Sums stay inside Int. At most 40,000 keys of at most 40,000 each add up to 1.6 billion, below the Int limit of about 2.1 billion. Because Int overflow wraps silently in Kotlin, this bound is what makes Int safe here.
    • minOf and maxOf. Both are used with two arguments, nested to compare three numbers.
    • var and val. isRootBST is the only local that is reassigned, so it is the only var in dfs.
    • if as an expression. if (isRootBST) 1 else 0 produces the flag stored in the array.

    Complexity

    Let n be the number of nodes and h the height of the tree.

    Time: O(n). dfs runs once for each node and once for each missing child, and every call does a constant amount of work: a few array reads, a few comparisons and one small array. No subtree is scanned twice. The first lesson on this problem scans subtrees again and again, which costs much more on some shapes.

    Space: O(h). The recursion keeps one frame per level of depth, along with small arrays that are discarded as the calls return. That is about log n for a balanced tree and up to n for a chain.

    Edge cases and common mistakes

    • All negative values. [-4, -2, -5] returns 0. The answer starts at 0 and no negative sum replaces it.
    • Equal keys. The test uses <= and >=, so a node equal to its left maximum or right minimum is not a BST root. This matches the strict rule in the statement.
    • Not returning the facts of a failed subtree. A node that isn't a BST still has to report its minimum, maximum and sum, together with the flag 0. The flag makes every ancestor fail too, because a BST can't contain a non-BST subtree.
    • Comparing only with the children. The checks use the largest key of the left subtree and the smallest of the right one, not the children's own values. For [10, 5, 15, null, null, 6, 20] the node 15 is a BST (sum 41), but the root fails since the smallest key on its right side is 6, which is below 10. The answer is 41.
    • Wrong sentinel direction. The empty subtree's minimum must be the biggest Int and its maximum the smallest. With the roles swapped, a leaf would compare its value against sentinels that always make it fail.
    • Updating result for every node. Only nodes whose flag is true may contribute. A larger sum from a non-BST would be wrong.

    Testing

    • [4, 3, null, 1, 2] gives 2.
    • [2, 1, 3] gives 6.
    • [-4, -2, -5] gives 0.
    • [5, 4, 8, 3, null, 6, 3] gives 7.
    • [10, 5, 15, null, null, 6, 20] gives 41.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free