Largest Bst in Binary Tree
Given a binary tree, find the size of the largest subtree that is a valid BST (the subtree must include all descendants of its root). The size is the number of nodes.
A whole tree that is a BST counts, and a single node is always a BST of size 1.
Intuition
1 102 / \3 5 154 / \ \5 1 8 7The subtree rooted at 5 (nodes 5, 1, 8) is a BST of size 3. The subtree rooted at 15 is not a BST because 7 is in its right subtree but is smaller than 15. The whole tree is not a BST either. The answer is 3.
For each node, a subtree is a BST if its left and right subtrees are both BSTs, the largest value on the left is smaller than the node, and the smallest value on the right is larger than the node. So each subtree needs to report three facts to its parent: its minimum, its maximum, and its size (when it is a BST).
This is a postorder idea: the answer for a node is built from the answers of its children.
Approach: Return (min, max, size) Bottom-Up
Write solve(node) that returns a triple (min, max, size):
- Empty tree: return
(+infinity, -infinity, 0). These bounds make an empty side never block the checks below. - Get
left = solve(node.left)andright = solve(node.right). - If
left.max < node.data < right.min, this whole subtree is a BST:min = min(node.data, left.min)max = max(node.data, right.max)size = left.size + right.size + 1
- Otherwise it is not a BST. Return
(-infinity, +infinity, max(left.size, right.size)). The impossible bounds guarantee that no ancestor can accept this subtree as part of a BST, while the size still carries the best BST found below. - The answer is
solve(root).size.
At every node, size is either the size of the BST rooted here or the largest BST found anywhere in its subtree, so the root's size is the final answer.
Code
class Solution {struct Info {int mn, mx, size;};Info solve(Node* node) {if (node == nullptr) return {INT_MAX, INT_MIN, 0};Info left = solve(node->left);Info right = solve(node->right);if (node->data > left.mx && node->data < right.mn) {return {min(node->data, left.mn),max(node->data, right.mx),left.size + right.size + 1};}return {INT_MIN, INT_MAX, max(left.size, right.size)};}public:int largestBst(Node* root) {return solve(root).size;}};
Complexity
Each node is visited once and does constant work. The brute force, validating a BST at every node, is O(n^2).
Recursion stack depth equals the tree height.