Size of the largest BST in a Binary Tree

Dec 18, 2024 • 5 mins read
Hero Image

Problem Overview

In this article, we will dive into the LeetCode problem titled "Maximum Sum BST in Binary Tree". This problem challenges us to determine the maximum sum of the values of nodes in any binary search tree (BST) that can be found within a given binary tree.

The essence of the problem is to identify subtrees that form a valid BST and then compute the maximum sum of their node values. This task encompasses tree traversal, validation of BST properties, and dynamic tracking of sums.

The problem can be found on LeetCode here.

Understanding the Problem

Given a binary tree, the task is to find the maximum sum of values in any subtree that qualifies as a BST. A subtree is considered a BST if, for every node:

  • The left subtree of a node has values less than the node's value.
  • The right subtree of a node has values greater than the node's value.
  • Both left and right subtrees must also be BSTs.

The goal is to efficiently identify such subtrees and calculate the maximum possible sum.

Example:

Input: [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
Output: 20
Explanation: The subtree with the maximum sum is: 
      3
     / \
    2   5
       / \
      4   6

Key DSA Concepts and Theory

1. Binary Trees and BSTs

  • Binary Tree: A tree data structure where each parent node has at most two children.
  • Binary Search Tree (BST): A special kind of binary tree where the left child's value is less than the parent's and the right child's value is greater than the parent's.

2. Tree Traversal

  • Postorder Traversal: We visit the left subtree, then the right subtree, followed by processing the root node. This is particularly useful for solving problems bottom-up, which is crucial for dynamic programming approaches in tree problems.

3. Dynamic Programming in Trees

  • Using postorder traversal, we can compute properties for nodes based on their child nodes, making it effective for evaluating and generating subtree results incrementally.

Solution Approach

To solve this problem, we will use a recursive approach leveraging postorder traversal to gather necessary details from the children nodes before making decisions at the parent node.

Steps:

  1. Postorder Traversal: Traverse the tree in a postorder fashion to process children before the node itself.
  2. BST Validation: For each node, check if the subtree rooted at that node is a BST.
  3. Sum Calculation and Update: Calculate the sum of valid BST subtrees and update the maximum sum accordingly.
  4. Return and Propagate Results: Use a tuple to propagate information upwards:
    • A boolean indicating if the subtree is a BST.
    • The sum of the BST subtree.
    • The smallest and largest values in the subtree to maintain BST properties.

Code Example

C++ Solution:

struct NodeInfo {
    bool isBST;
    int sum;
    int minVal;
    int maxVal;
};

class Solution {
private:
    int maxSum = 0;
    
    NodeInfo postorder(TreeNode* node) {
        if (!node) return {true, 0, INT_MAX, INT_MIN};

        auto left = postorder(node->left);
        auto right = postorder(node->right);

        if (left.isBST && right.isBST && node->val > left.maxVal && node->val < right.minVal) {
            int subTreeSum = left.sum + right.sum + node->val;
            maxSum = std::max(maxSum, subTreeSum);
            return {true, subTreeSum, std::min(left.minVal, node->val), std::max(right.maxVal, node->val)};
        }

        return {false, 0, 0, 0};
    }
    
public:
    int maxSumBST(TreeNode* root) {
        postorder(root);
        return maxSum;
    }
};

Java Solution:

class Solution {
    private class NodeInfo {
        boolean isBST;
        int sum;
        int minVal;
        int maxVal;
        
        NodeInfo(boolean isBST, int sum, int minVal, int maxVal) {
            this.isBST = isBST;
            this.sum = sum;
            this.minVal = minVal;
            this.maxVal = maxVal;
        }
    }
    
    private int maxSum = 0;
    
    public int maxSumBST(TreeNode root) {
        postorder(root);
        return maxSum;
    }
    
    private NodeInfo postorder(TreeNode node) {
        if (node == null) return new NodeInfo(true, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
        
        NodeInfo left = postorder(node.left);
        NodeInfo right = postorder(node.right);
        
        if (left.isBST && right.isBST && node.val > left.maxVal && node.val < right.minVal) {
            int subTreeSum = left.sum + right.sum + node.val;
            maxSum = Math.max(maxSum, subTreeSum);
            return new NodeInfo(true, subTreeSum, Math.min(left.minVal, node.val), Math.max(right.maxVal, node.val));
        }

        return new NodeInfo(false, 0, 0, 0);
    }
}

Time and Space Complexity Analysis

  • Time Complexity: O(N), where N is the number of nodes in the binary tree. This is because in the worst case, we traverse each node once.
  • Space Complexity: O(H), where H is the height of the binary tree, representing the recursion stack space. In the worst case, for a skewed tree, H could be N.

Common Mistakes to Avoid

  • Incorrect Update Logic: Make sure to only update the maximum sum if the subtree is a valid BST.
  • Boundary Conditions: Thoroughly handle NULL nodes and ensure correct initialization of min and max values.
  • Comparing Node Values: Ensure the BST property comparison, node->val > left.maxVal && node->val < right.minVal, is correctly implemented.

Similar Problems on LeetCode

  • LeetCode 230 - Kth Smallest Element in a BST
  • LeetCode 538 - Convert BST to Greater Tree
  • LeetCode 653 - Two Sum IV - Input is a BST

Additional Resources and References