We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Largest BST Subtree

Number: 333

Difficulty: Medium

Paid? Yes

Companies: Meta, TikTok, Microsoft

Problem Description

Given the root of a binary tree, find the largest subtree which is also a Binary Search Tree (BST) by the number of nodes. A BST is defined such that for every node, all nodes in its left subtree have values less than the node’s value, and all nodes in its right subtree have values greater than the node’s value. The subtree must include all of its descendants.

Key Insights

  • Use a bottom-up DFS (post-order traversal) to process each node.
  • For each node, determine whether its left and right subtrees are BSTs.
  • Maintain additional data per subtree: size (number of nodes), minimum value, and maximum value.
  • A subtree rooted at the current node is a BST if:
    • Its left subtree is a BST.
    • Its right subtree is a BST.
    • The maximum value in the left subtree is less than the current node’s value.
    • The current node’s value is less than the minimum value in the right subtree.
  • Track the size of the largest BST identified during the traversal.

Space and Time Complexity

Time Complexity: O(n) (each node is visited once)
Space Complexity: O(h), where h is the height of the tree (due to recursion stack)

Solution

Perform a post-order traversal of the binary tree. For each node, return a tuple (or object in some languages) that provides:

  • Whether the subtree rooted at this node is a BST.
  • The size of the subtree if it is a BST (or the size of the largest BST found within it).
  • The minimum value in the subtree.
  • The maximum value in the subtree.

At each node, if both left and right children form valid BSTs and the current node’s value fits the BST condition (greater than left’s max and less than right’s min), then the subtree rooted at the node is also a BST. Calculate its size and update the current global maximum if necessary. If the condition fails, return the maximum BST size found in its subtrees.

Code Solutions

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def largestBSTSubtree(self, root: TreeNode) -> int:
        # Global variable to store the size of the largest BST subtree found.
        self.max_bst_size = 0
        
        def helper(node):
            # Returns a tuple of: (isBST, size, min_val, max_val)
            if not node:
                # An empty node is considered a BST of size 0 with extreme min and max values.
                return (True, 0, float('inf'), float('-inf'))
            
            left_is_bst, left_size, left_min, left_max = helper(node.left)
            right_is_bst, right_size, right_min, right_max = helper(node.right)
            
            # Check if the current node forms a BST with its left and right subtrees.
            if left_is_bst and right_is_bst and node.val > left_max and node.val < right_min:
                current_size = left_size + right_size + 1
                self.max_bst_size = max(self.max_bst_size, current_size)
                current_min = min(left_min, node.val)
                current_max = max(right_max, node.val)
                return (True, current_size, current_min, current_max)
            else:
                # Not a BST: Return false and the size of the largest BST found so far in its subtrees.
                return (False, max(left_size, right_size), 0, 0)
        
        helper(root)
        return self.max_bst_size
← Back to All Questions