Largest BST subtree in a binary tree
Problem
Return the number of nodes in the largest subtree that is itself a valid BST.
Example 1
Input: [10, 5, 15, 1, 8, null, 7] Output: 3
The subtree rooted at 5: {5, 1, 8}.
Also asked as: Largest BST in a Binary Tree
Test cases
Case 1
Input: [10,5,15,1,8,null,7] Expected: 3
Case 2
Input: [2,1,3] Expected: 3
Case 3
Input: [5,6,4] Expected: 1
Case 4
Input: [] Expected: 0
View solutionHide solution1 approach
1. Post-order returning (isBST, size, min, max)
Time O(n)Space O(h)
A node forms a BST iff both children are BSTs and node.val > leftMax and node.val < rightMin. Track the largest size seen.
function largestBSTSubtree(root) { let best = 0; const dfs = (n) => { if (!n) return { isBST: true, size: 0, min: Infinity, max: -Infinity }; const L = dfs(n.left), R = dfs(n.right); if (L.isBST && R.isBST && n.val > L.max && n.val < R.min) { const size = L.size + R.size + 1; best = Math.max(best, size); return { isBST: true, size, min: Math.min(n.val, L.min), max: Math.max(n.val, R.max) }; } return { isBST: false, size: 0, min: 0, max: 0 }; }; dfs(root); return best;}