# 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:
self.max_bst = 0
def helper(node):
if not node:
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)
if left_is_bst and right_is_bst and left_max < node.val < right_min:
size = left_size + right_size + 1
self.max_bst = max(self.max_bst, size)
return (True, size, min(left_min, node.val), max(right_max, node.val))
else:
return (False, 0, 0, 0)
helper(root)
return self.max_bst
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int max_bst = 0;
// Returns tuple: isBST, size, min, max
std::tuple helper(TreeNode* node) {
if (!node)
return std::make_tuple(true, 0, INT_MAX, INT_MIN);
auto [left_bst, left_size, left_min, left_max] = helper(node->left);
auto [right_bst, right_size, right_min, right_max] = helper(node->right);
if (left_bst && right_bst && left_max < node->val && node->val < right_min) {
int size = left_size + right_size + 1;
max_bst = std::max(max_bst, size);
int min_val = std::min(left_min, node->val);
int max_val = std::max(right_max, node->val);
return std::make_tuple(true, size, min_val, max_val);
}
return std::make_tuple(false, 0, 0, 0);
}
int largestBSTSubtree(TreeNode* root) {
helper(root);
return max_bst;
}
};
// Definition for a binary tree node.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
int maxBST = 0;
// Returns int[]: {isBST:1/0, size, min, max}
private int[] helper(TreeNode node) {
if (node == null)
return new int[]{1, 0, Integer.MAX_VALUE, Integer.MIN_VALUE};
int[] left = helper(node.left);
int[] right = helper(node.right);
if (left[0] == 1 && right[0] == 1 && left[3] < node.val && node.val < right[2]) {
int size = left[1] + right[1] + 1;
maxBST = Math.max(maxBST, size);
int min = Math.min(left[2], node.val);
int max = Math.max(right[3], node.val);
return new int[]{1, size, min, max};
}
return new int[]{0, 0, 0, 0};
}
public int largestBSTSubtree(TreeNode root) {
helper(root);
return maxBST;
}
}
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
var largestBSTSubtree = function(root) {
let maxBST = 0;
function helper(node) {
if (!node) return [true, 0, Infinity, -Infinity];
let [lBST, lSize, lMin, lMax] = helper(node.left);
let [rBST, rSize, rMin, rMax] = helper(node.right);
if (lBST && rBST && lMax < node.val && node.val < rMin) {
let size = lSize + rSize + 1;
maxBST = Math.max(maxBST, size);
return [true, size, Math.min(lMin, node.val), Math.max(rMax, node.val)];
} else {
return [false, 0, 0, 0];
}
}
helper(root);
return maxBST;
};
You are given the root of a binary tree. Your task is to find the size (number of nodes) of the largest subtree that is a Binary Search Tree (BST). A subtree is any node and all its descendants in the tree. A BST is defined as a binary tree in which for every node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater than the node's value.
root node.To solve this problem, we first need to understand that not every subtree in a binary tree is a BST. The naive approach would be to check every possible subtree and verify if it is a BST, then keep track of the largest one. However, this would be very inefficient, especially for large trees.
We can improve on this by using recursion. For each node, we can recursively determine whether its left and right subtrees are BSTs, and if so, whether combining them with the current node still satisfies the BST property. If it does, we can calculate the size of this BST. If not, we keep the maximum size found in any of its subtrees.
The key insight is that for each node, we need to know:
We use a recursive, bottom-up (post-order) traversal of the tree. At each node, we gather information from its left and right children. Here are the steps:
This approach ensures that each node is visited only once, and all necessary information is passed up the tree efficiently.
Let's consider the following binary tree:
10
/ \
5 15
/ \ \
1 8 7
Brute-force Approach: For every node, check every possible subtree and validate if it's a BST, which could take O(N^2) time in the worst case (where N is the number of nodes).
Optimized Approach (this solution): Each node is visited exactly once, and all necessary information is computed and propagated in O(1) time per node. Therefore, the total time complexity is O(N).
The space complexity is O(H), where H is the height of the tree, due to the recursion stack. In the worst case (skewed tree), this is O(N); in a balanced tree, O(log N).
The key to solving the Largest BST Subtree problem efficiently is to use a post-order traversal, gathering information about each subtree as we return from recursion. By keeping track of whether subtrees are BSTs and their sizes, as well as the min and max values, we can determine in constant time per node whether a larger BST has been found. This approach is both elegant and efficient, reducing the time complexity from O(N^2) to O(N).