PPractick

The problem

A data-quality tool scans a binary tree that is supposed to be a BST but has been corrupted in places, and it reports the largest subtree that is still a valid BST (counting nodes), so that part can be salvaged. Checking every subtree separately is O(n²). A single post-order pass does it in O(n). Each node gets from its children whether they're BSTs, their sizes, and their minimum and maximum keys. The node forms a BST exactly when both children do and left max < node < right min.

Example: [10, 5, 15, 1, 8, null, 7] → 3 (the subtree 5, 1, 8).

Function signature

int largestBST(TreeNode* root);  // number of nodes in the largest BST subtree

Test cases

Input (level order)	Output	Explanation
[10, 5, 15, 1, 8, null, 7]	3	7 under 15 breaks the right side
[5, 2, 4, 1, 3]	3	4 is on the right of 5 but smaller
[3, 1, 5, 0, 2, 4, 6]	7	The whole tree
[1]	1
[]	0

(Confirm: a subtree means a node with all its descendants; BST ordering is strict.)

How interviewers phrase it

• "Given a binary tree, find the size of the largest subtree which is also a BST" (GeeksforGeeks "Largest BST"; LeetCode 333).

Clarifying questions to ask

1. Does "subtree" mean a node plus all descendants? (Yes, not an arbitrary connected piece.)
2. Is ordering strict? (Yes.)
3. Return the size, or the root? (The size.)

Follow-ups to expect

1. "Brute force?"
2. "What does each call return in the O(n) solution?"
3. "Why return a failing tuple when not a BST?"
4. "How do empty children fit?"
5. "Complexity?"

Related questions

• Correct BST with two nodes swapped Hard
• Count Good Numbers Medium
• Word Break Medium
• Search in a Binary Search Tree Easy
• Floor and Ceil in a BST Easy
• Floor in a Binary Search Tree Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in