Find the Largest Search-Tree Piece Inside a Tree
Solve this ProblemYou are given the root of a binary tree that is not necessarily a search tree. A subtree (a node together with all its descendants) is a valid binary search tree if, at every node in it, all values in the left part are strictly smaller and all values in the right part strictly larger than the node's value. Return the number of nodes in the largest subtree that is a valid binary search tree.
Checking every subtree separately repeats a lot of work. One bottom-up pass in which each subtree reports whether it is a search tree, its size, and its smallest and largest values gives the answer in linear time.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100; −1000 ≤ node.val ≤ 1000; values may repeat - ◆
The tree is a general binary tree given by its root node (null for an empty tree); it does NOT have to be a search tree - ◆
A subtree is a node together with ALL of its descendants. It is a valid binary search tree when for every node in it, all values in its left part are strictly smaller and all values in its right part are strictly larger - ◆
Return the number of nodes in the LARGEST subtree of the tree that is a valid binary search tree (a single node always qualifies; an empty tree gives 0)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Check Whether the Whole Subtree Is a Search Tree, Then Recurse
BruteIf the tree rooted at the current node is a valid search tree, it is the biggest one containing this node — its answer is its number of nodes. Otherwise the answer must come from inside one of the two children, so take the larger of the two children's answers. Each "is it a search tree?" check walks the whole subtree, and it is repeated at every level of the recursion, so the total work is O(n²) on a tall tree; the recursion adds O(h) space.
O(n²)O(h)1class Solution {
2 public int largestBstSize(TreeNode root) {
3 if (root == null) return 0;
4 if (valid(root, Long.MIN_VALUE, Long.MAX_VALUE)) return count(root);
5 return Math.max(largestBstSize(root.left), largestBstSize(root.right));
6 }
7
8 private boolean valid(TreeNode node, long low, long high) {
9 if (node == null) return true;
10 if (node.val <= low || node.val >= high) return false;
11 return valid(node.left, low, node.val) && valid(node.right, node.val, high);
12 }
13
14 private int count(TreeNode node) {
15 if (node == null) return 0;
16 return 1 + count(node.left) + count(node.right);
17 }
18}Optimal — One Post-Order Pass Returning (isBst, size, min, max)
OptimalSolve every subtree bottom-up and report four facts to the parent: whether the subtree is a valid search tree, its size, and its smallest and largest values. An empty subtree is a valid tree of size 0 whose min is +∞ and max is −∞ (so it never blocks a comparison). A node forms a search tree when both child subtrees are search trees, the LARGEST value on the left is smaller than the node and the SMALLEST value on the right is larger than it; then its size is left + right + 1, its min is min(left min, node) and its max is max(right max, node), and the global best is updated. Otherwise it reports "not a search tree" (and its parents cannot be search trees either). Every node is handled once: O(n) time, O(h) space.
O(n)O(h)1class Solution {
2 private int best;
3
4 public int largestBstSize(TreeNode root) {
5 best = 0;
6 info(root);
7 return best;
8 }
9
10 // returns {isBst (1/0), size, min, max} for the subtree
11 private int[] info(TreeNode node) {
12 if (node == null) return new int[]{1, 0, Integer.MAX_VALUE, Integer.MIN_VALUE};
13 int[] left = info(node.left);
14 int[] right = info(node.right);
15 if (left[0] == 1 && right[0] == 1 && left[3] < node.val && node.val < right[2]) {
16 int size = left[1] + right[1] + 1;
17 best = Math.max(best, size);
18 return new int[]{1, size, Math.min(left[2], node.val), Math.max(right[3], node.val)};
19 }
20 return new int[]{0, 0, 0, 0};
21 }
22}