What is the time complexity of Maximum Sum BST in Binary Tree?

The optimal solution has a time complexity of O(N).

What data structures are used to solve Maximum Sum BST in Binary Tree?

This problem uses Dynamic Programming, Tree, Depth-First Search, Binary Search Tree, Binary Tree. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Maximum Sum BST in Binary Tree?

Insight 1: Post-order traversal allows us to determine if a subtree is a BST and calculate its sum bottom-up. Insight 2: We need to track not only if a subtree is a BST, but also the minimum and maximum values within that subtree for efficient validation at each node.

Which companies ask LeetCode 1373. Maximum Sum BST in Binary Tree in interviews?

This problem is frequently asked at Zepto.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Maximum Sum BST in Binary Tree - LeetCode 1373 Solution

Maximum Sum BST in Binary Tree - Complete Solution Guide

Maximum Sum BST in Binary Tree is LeetCode problem 1373, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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

Detailed Explanation

The problem asks us to find the maximum sum of keys within any subtree of a given binary tree, but with the added constraint that this subtree must also be a Binary Search Tree (BST). A BST has the property that for each node, all keys in its left subtree are smaller than the node's key, and all keys in its right subtree are larger. We need to traverse the tree, identify all valid BST subtrees, calculate their sums, and return the maximum sum encountered.

Solution Approach

The solution uses a post-order Depth-First Search (DFS) traversal of the binary tree. For each node, it recursively checks if its left and right subtrees are BSTs. If both are BSTs and the node's value is within the valid range (greater than the maximum value of the left subtree and smaller than the minimum value of the right subtree), then the current subtree is also a BST. The sum of this BST is calculated, and the global maximum sum is updated. If any subtree is not a BST, the node is marked as not being part of any BST, and the search continues.

Step-by-Step Algorithm

Step 1: Define a recursive helper function `traverse(node)` that performs a post-order traversal.
Step 2: Base Case: If the current `node` is null, return a `Result` object indicating it's a BST (vacuously true), with minimum value as infinity, maximum value as negative infinity, and sum as 0.
Step 3: Recursively call `traverse` on the left and right children of the current `node` to get their respective `Result` objects (which contain BST status, min/max values, and subtree sum).
Step 4: Check if the current subtree, including the current `node`, forms a valid BST. This is true if: a) both left and right subtrees are BSTs, b) the current node's value is greater than the maximum value in the left subtree, and c) the current node's value is less than the minimum value in the right subtree.
Step 5: If the current subtree is a BST, calculate its sum by adding the current node's value to the sums of its left and right subtrees. Update the global maximum sum if the current subtree's sum is larger. Also, determine the new minimum and maximum values for the current subtree (the minimum of the left subtree's minimum and the node's value, and the maximum of the right subtree's maximum and the node's value, respectively). Return a Result object indicating that it is a BST, the min, max, and sum.
Step 6: If the current subtree is NOT a BST (any of the conditions in Step 4 are false), then return a `Result` object indicating that it's not a BST, setting min as negative infinity, max as positive infinity, and sum to 0. This prevents the parent node from considering it a BST.
Step 7: The `maxSumBST` function initializes the `max_sum` to 0 and calls the `traverse` function on the root. Finally, it returns the `max_sum`.

Key Insights

Insight 1: Post-order traversal allows us to determine if a subtree is a BST and calculate its sum bottom-up.
Insight 2: We need to track not only if a subtree is a BST, but also the minimum and maximum values within that subtree for efficient validation at each node.
Insight 3: The solution must handle cases where the entire tree is not a BST, or contains only negative values, potentially resulting in a maximum BST sum of 0.

Complexity Analysis

Time Complexity: O(N)

Space Complexity: O(H)

Topics

This problem involves: Dynamic Programming, Tree, Depth-First Search, Binary Search Tree, Binary Tree.

Companies

Asked at: Zepto.

Maximum Sum BST in Binary Tree | LeetCode 1373

Hard

Dynamic Programming Tree Depth-First Search Binary Search Tree Binary Tree

Time: O(N)Space: O(H)

Solution Code

Available in:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int max_sum = 0;

    public int maxSumBST(TreeNode root) {
        max_sum = 0;
        traverse(root);
        return max_sum;
    }

    private Result traverse(TreeNode node) {
        if (node == null) {
            return new Result(true, Integer.MAX_VALUE, Integer.MIN_VALUE, 0);
        }

        Result leftResult = traverse(node.left);
        Result rightResult = traverse(node.right);

        if (leftResult.isBST && rightResult.isBST && leftResult.max < node.val && node.val < rightResult.min) {
            int current_sum = node.val + leftResult.sum + rightResult.sum;
            max_sum = Math.max(max_sum, current_sum);

            int min_val = Math.min(node.val, leftResult.min);
            int max_val = Math.max(node.val, rightResult.max);

            return new Result(true, min_val, max_val, current_sum);
        } else {
            return new Result(false, Integer.MIN_VALUE, Integer.MAX_VALUE, 0);
        }
    }

    private class Result {
        boolean isBST;
        int min;
        int max;
        int sum;

        public Result(boolean isBST, int min, int max, int sum) {
            this.isBST = isBST;
            this.min = min;
            this.max = max;
            this.sum = sum;
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1373: Maximum Sum BST in Binary Tree - Detailed explanation and solution approaches.

Topics

Dynamic Programming Tree Depth-First Search Binary Search Tree Binary Tree

Companies

Zepto

Stats

Difficulty:Hard

Languages:4

Companies:1

Problem #:1373

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Define a recursive helper function `traverse(node)` that performs a post-order traversal.
2
Step 2: Base Case: If the current `node` is null, return a `Result` object indicating it's a BST (vacuously true), with minimum value as infinity, maximum value as negative infinity, and sum as 0.
3
Step 3: Recursively call `traverse` on the left and right children of the current `node` to get their respective `Result` objects (which contain BST status, min/max values, and subtree sum).
4
Step 4: Check if the current subtree, including the current `node`, forms a valid BST. This is true if: a) both left and right subtrees are BSTs, b) the current node's value is greater than the maximum value in the left subtree, and c) the current node's value is less than the minimum value in the right subtree.
5
Step 5: If the current subtree is a BST, calculate its sum by adding the current node's value to the sums of its left and right subtrees. Update the global maximum sum if the current subtree's sum is larger. Also, determine the new minimum and maximum values for the current subtree (the minimum of the left subtree's minimum and the node's value, and the maximum of the right subtree's maximum and the node's value, respectively). Return a Result object indicating that it is a BST, the min, max, and sum.
6
Step 6: If the current subtree is NOT a BST (any of the conditions in Step 4 are false), then return a `Result` object indicating that it's not a BST, setting min as negative infinity, max as positive infinity, and sum to 0. This prevents the parent node from considering it a BST.
7
Step 7: The `maxSumBST` function initializes the `max_sum` to 0 and calls the `traverse` function on the root. Finally, it returns the `max_sum`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(N)

💾

Space Complexity

O(H)

📝

Why?

The time complexity is determined by the traversal of all nodes in the tree. The space complexity is governed by the maximum depth of the recursion, which depends on the height of the tree.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Iterative Approach with Stack

An iterative approach using a stack to simulate the post-order traversal. This eliminates recursion and can be useful for languages with limited stack size.

Time: O(N)Space: O(N) in the worst case (skewed tree), O(log N) in average case (balanced tree)

Trade-offs: The iterative approach might be slightly more complex to implement compared to the recursive approach, but it avoids potential stack overflow issues for very deep trees. The space complexity might be slightly higher if the tree is skewed.

✨

Key Insights

1Insight 1: Post-order traversal allows us to determine if a subtree is a BST and calculate its sum bottom-up.
2Insight 2: We need to track not only if a subtree is a BST, but also the minimum and maximum values within that subtree for efficient validation at each node.
3Insight 3: The solution must handle cases where the entire tree is not a BST, or contains only negative values, potentially resulting in a maximum BST sum of 0.

📚

Key Terms Explained

For Students

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Tree

Hierarchical structure with nodes. Like a family tree!

Edge Cases

Edge case 1: Empty tree (root is None). The algorithm correctly handles this case as the base case of the recursion returns 0, indicating an empty BST with a sum of 0.
Edge case 2: Tree with only negative values. The algorithm correctly calculates the maximum BST sum as 0 if no positive-sum BST is found.
Edge case 3: A single node is a valid BST. The algorithm identifies this and returns the node's value if it's the largest BST sum found so far.
Edge case 4: Skewed tree. The algorithm still processes all nodes correctly, although the space complexity increases due to the depth of the recursion.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly checking BST property. Failing to compare the current node's value with the maximum value of the left subtree and the minimum value of the right subtree. Forgetting to handle edge cases like empty subtrees, resulting in wrong BST validation.

✗Common mistake 2: Not initializing the global `max_sum` variable correctly. If not initialized to zero, the algorithm might return garbage values.

✗Common mistake 3: Not considering negative values. Incorrectly assuming the maximum sum will always be positive. The code needs to handle the case where all possible BST sums are negative and return 0 in such cases.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Database indexing: BSTs are fundamental in database indexing to efficiently search and retrieve data. Identifying the largest BST within a complex data structure could be used to optimize search strategies.

🏦Real-world scenario 2: Compiler design: Representing expressions as trees. The algorithm could be adapted to find the largest valid expression subtree for optimization purposes.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Start with recursion, then memoize. The hardest part is identifying the state. Ask yourself: "What information do I need to make the current decision?"

🎯 Interview Tip

These problems test your ability to optimize. Start with a brute force solution, then improve.

⚠️ Watch Out

Forgetting base cases or initializing the DP array incorrectly. Start by solving the smallest subproblems.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 22, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 13

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 6

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jun 29

❓

Frequently Asked Questions

Should I use top-down (memoization) or bottom-up (tabulation)?

Start with top-down (recursion + memoization) as it directly maps to the recursive thinking and handles only needed subproblems. Convert to bottom-up for better space efficiency and to avoid stack overflow. Bottom-up is often faster due to no recursion overhead.

What is the difference between DFS and BFS for trees?

DFS (using recursion or stack) explores depth-first, useful for path-finding and backtracking problems. BFS (using queue) explores level-by-level, ideal for finding shortest paths or processing nodes by depth. Choose based on whether level information matters.

Is it okay to not fully solve hard problems in interviews?

Yes! Interviewers care more about your problem-solving process than the final answer. Demonstrate: clear communication, systematic approach, ability to recognize when to pivot strategies, and graceful handling of hints. Partial progress with good reasoning is valued.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Maximum Sum BST in Binary Tree"?

For this hard-level Dynamic Programming problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether tree techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?