Largest BST subtree in a binary tree

Hard

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}