DSA problem
Largest BST Subtree
Given the root of a binary tree (NOT necessarily a BST), find the largest subtree that is itself a Binary Search Tree, where "largest" means the most nodes. Return the size of that subtree.
A subtree must include every descendant of the chosen root. A subtree is a valid BST if for every node in it, all left descendants are strictly less than the node and all right descendants are strictly greater. The single-node tree is trivially a BST of size 1.
A naive solution checks each subtree independently: at every node, validate whether it is a BST in O(n) and count its size, costing O(n^2) overall. Worse, that validation has to look at all descendants from scratch each time.
The optimal approach is a single post-order DFS that returns four pieces of information about each subtree: whether it is a valid BST, its size if so, and its minimum and maximum values. From the children's reports we can decide the current subtree in O(1): it is a BST iff both children are BSTs AND leftMax < root.val < rightMin. When valid, its size is leftSize + rightSize + 1, its min is leftMin if left exists else root.val, and its max is rightMax if right exists else root.val. A global best variable tracks the largest size encountered. The whole traversal runs in O(n) time and O(h) recursion space.
Examples
root = [10,5,15,1,8,null,7]3root = [4,2,7,2,3,5,null,2,null,null,null,null,null,1]2root = [1]1Constraints
- The number of nodes in the tree is in the range [0, 10^4].
- -10^4 <= Node.val <= 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.