Log inSign up
hardGeeksforGeeksNot Started

Largest BST in a Binary Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a Binary Tree, find the size of the largest subtree which is also a Binary Search Tree (BST). If the tree, itself, is a BST, then the returned size will refer to the total size of the tree.

Size of a subtree refers to the total number of nodes contained within that subtree.

A subtree must satisfy: - Left subtree of a node contains only nodes with keys less than the node's key. - Right subtree of a node contains only nodes with keys greater than the node's key. - Both left and right subtrees must also be binary search trees.

Constraints:

  • 1 <= Number of nodes <= 105
  • 1 <= Data of a node <= 106

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why top-down BST validation causes O(N2) redundancy.
  • Design the 4-tuple state { isBst, size, min, max } for post-order DFS.
  • Master the neutral identity elements (min = +INF, max = -INF) for null nodes.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find largest BST inside a general Binary Tree.
  • Check BST property for all subtrees.
  • Subtree size optimization.

Algorithmic Decision Tree:

  • Use Post-Order DFS returning struct { isBst, size, minVal, maxVal }.
  • Base case null: { isBst: true, size: 0, minVal: +INF, maxVal: -INF }.
  • Validate: curr.data > left.max && curr.data < right.min.

Connected Patterns:

Validate Binary Search TreeMaximum Sum BST in Binary TreeDiameter of Binary Tree

1. Top-Down Subtree Validation (O(N^2))

Intuition

For each node in the tree: 1. Check if the subtree rooted at curr is a valid BST by verifying that all values in left subtree are < curr.data and all values in right subtree are > curr.data. 2. If it is a valid BST, count its nodes and return that size. 3. If it is not a valid BST, recursively return max(largestBst(curr.left), largestBst(curr.right)). Because testing BST validity takes O(N) at every node, total time is O(N2) on skewed trees.

When to apply: Baseline brute-force explanation to contrast against bottom-up aggregation.

Algorithm

  1. For every node, run isBST(node) in O(size) time. If true, count its size; otherwise recurse on children.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <climits>
3#include <algorithm>
4
5struct Node {
6 int data;
7 Node* left;
8 Node* right;
9 Node(int val) : data(val), left(nullptr), right(nullptr) {}
10};
11
12class Solution {
13 bool isBST(Node* root, long long minVal, long long maxVal) {
14 if (!root) return true;
15 if (root->data <= minVal || root->data >= maxVal) return false;
16 return isBST(root->left, minVal, root->data) && isBST(root->right, root->data, maxVal);
17 }
18
19 int size(Node* root) {
20 if (!root) return 0;
21 return 1 + size(root->left) + size(root->right);
22 }
23public:
24 int largestBst(Node* root) {
25 if (!root) return 0;
26 if (isBST(root, LLONG_MIN, LLONG_MAX)) {
27 return size(root);
28 }
29 return std::max(largestBst(root->left), largestBst(root->right));
30 }
31};
32
33int main() {
34 Node* root = new Node(50);
35 root->left = new Node(30);
36 root->right = new Node(60);
37 root->left->left = new Node(5);
38 root->left->right = new Node(20);
39 root->right->left = new Node(45);
40 root->right->right = new Node(70);
41 root->right->right->left = new Node(65);
42 root->right->right->right = new Node(80);
43
44 Solution sol;
45 std::cout << "Largest BST size: " << sol.largestBst(root) << std::endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(N^2) worst case
  • Space complexity: O(H) recursion stack space

2. Memoized Subtree Validation

Intuition

Store subtree validation results in a hash map mapping Node* -> { isBst, size }. While memoization prevents repeating identical subproblems, computing bounds still visits child nodes redundantly without bottom-up tuple passing.

When to apply: Intermediate optimization to demonstrate understanding of overlapping subproblems.

Algorithm

  1. Cache validation results in a hash table to avoid duplicate checks.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <climits>
3#include <unordered_map>
4#include <algorithm>
5
6struct Node {
7 int data;
8 Node* left;
9 Node* right;
10 Node(int val) : data(val), left(nullptr), right(nullptr) {}
11};
12
13class Solution {
14 std::unordered_map<Node*, int> memo;
15
16 bool isBST(Node* root, long long minVal, long long maxVal) {
17 if (!root) return true;
18 if (root->data <= minVal || root->data >= maxVal) return false;
19 return isBST(root->left, minVal, root->data) && isBST(root->right, root->data, maxVal);
20 }
21
22 int size(Node* root) {
23 if (!root) return 0;
24 return 1 + size(root->left) + size(root->right);
25 }
26public:
27 int largestBst(Node* root) {
28 if (!root) return 0;
29 if (memo.count(root)) return memo[root];
30
31 if (isBST(root, LLONG_MIN, LLONG_MAX)) {
32 return memo[root] = size(root);
33 }
34 return memo[root] = std::max(largestBst(root->left), largestBst(root->right));
35 }
36};
37
38int main() {
39 Node* root = new Node(50);
40 root->left = new Node(30);
41 root->right = new Node(60);
42 root->left->left = new Node(5);
43 root->left->right = new Node(20);
44 root->right->left = new Node(45);
45 root->right->right = new Node(70);
46 root->right->right->left = new Node(65);
47 root->right->right->right = new Node(80);
48
49 Solution sol;
50 std::cout << "Largest BST size: " << sol.largestBst(root) << std::endl;
51 return 0;
52}

Time & Space Complexity

  • Time complexity: O(N^2) in worst case
  • Space complexity: O(N) memoization table

3. Bottom-Up Post-Order DFS Aggregation

Intuition

1. For each node, recursively evaluate both children first (Post-Order). 2. Base case (null): return { isBst: true, size: 0, minVal: +INF, maxVal: -INF }. 3. A node curr forms a BST with its subtrees iff: - left.isBst == true and right.isBst == true - curr.data > left.maxVal and curr.data < right.minVal 4. If valid BST: - Return { isBst: true, size: 1 + left.size + right.size, minVal: min(curr.data, left.minVal), maxVal: max(curr.data, right.maxVal) }. 5. If invalid BST: - Return { isBst: false, size: max(left.size, right.size), minVal: -INF, maxVal: +INF }. Every node is visited exactly once -> strictly O(N) time and O(H) recursion stack space.

When to apply: The definitive gold standard for technical interviews and competitive programming.

Algorithm

  1. Post-order DFS returns { isBst, size, minVal, maxVal }. Validates current node in O(1) from children, achieving linear O(N) time.

Bottom-Up DFS Aggregation Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
dfs(20): Leaf -> isBst=true, size=1, min=20, max=20
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Check / comparison
dfs(5): Leaf -> isBst=true, size=1, min=5, max=5
Decision / next transition
1
Why this step matters

dfs(20): Leaf -> isBst=true, size=1, min=20, max=20

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <climits>
3#include <algorithm>
4
5struct Node {
6 int data;
7 Node* left;
8 Node* right;
9 Node(int val) : data(val), left(nullptr), right(nullptr) {}
10};
11
12struct SubtreeInfo {
13 bool isBst;
14 int size;
15 long long minVal;
16 long long maxVal;
17};
18
19class Solution {
20 SubtreeInfo dfs(Node* root) {
21 if (!root) {
22 return { true, 0, LLONG_MAX, LLONG_MIN };
23 }
24
25 SubtreeInfo left = dfs(root->left);
26 SubtreeInfo right = dfs(root->right);
27
28 // Check if current node forms a BST
29 if (left.isBst && right.isBst && root->data > left.maxVal && root->data < right.minVal) {
30 return {
31 true,
32 1 + left.size + right.size,
33 std::min((long long)root->data, left.minVal),
34 std::max((long long)root->data, right.maxVal)
35 };
36 }
37
38 // Not a BST
39 return {
40 false,
41 std::max(left.size, right.size),
42 LLONG_MIN,
43 LLONG_MAX
44 };
45 }
46public:
47 int largestBst(Node* root) {
48 return dfs(root).size;
49 }
50};
51
52int main() {
53 Node* root = new Node(50);
54 root->left = new Node(30);
55 root->right = new Node(60);
56 root->left->left = new Node(5);
57 root->left->right = new Node(20);
58 root->right->left = new Node(45);
59 root->right->right = new Node(70);
60 root->right->right->left = new Node(65);
61 root->right->right->right = new Node(80);
62
63 Solution sol;
64 std::cout << "Largest BST size: " << sol.largestBst(root) << std::endl;
65 return 0;
66}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(H) recursion stack space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Top-Down Subtree Validation (O(N2))O(N^2) worst caseO(H) recursion stack spaceFor every node, run isBST(node) in O(size) time. If true, count its size; otherwise recurse on children.O(N2) worst case
2.Memoized Subtree ValidationO(N^2) in worst caseO(N) memoization tableCache validation results in a hash table to avoid duplicate checks.O(N2) in worst case
3.Bottom-Up Post-Order DFS AggregationOptimalO(N)O(H) recursion stack spacePost-order DFS returns { isBst, size, minVal, maxVal }. Validates current node in O(1) from children, achieving linear O(N) time.O(N)

Common Pitfalls & Crucial Edge Cases

Checking only immediate children

Comparing root.data > root.left.data instead of the maximum of the entire left subtree (root.data > left.maxVal).

Reversing INF bounds on base case

Setting minVal = -INF for null makes every left leaf fail validation.

Propagating size incorrectly on invalid BST

When invalid, must return max(left.size, right.size) so the largest valid BST found so far is not lost.

Crucial Edge Cases to Validate:

  • Entire Binary Tree is already a valid BST — Returns total number of nodes N.
  • No subtree larger than 1 node is a BST — Returns 1 (each individual leaf is a valid BST of size 1).
  • Single node tree — Returns 1.
  • Tree contains extreme integer values (-10^6 or 10^6) — Handled safely with long long infinity bounds.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the flaw of the top-down O(N2) approach before presenting the optimal bottom-up solution.
  2. Write down the 4-tuple state { isBst, size, min, max } on the whiteboard or editor.
  3. Explain the clever base case (min = +INF, max = -INF) which naturally handles missing children without special if (root.left == null) branches.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must the base case for a null node return minVal = +INF and maxVal = -INF?

2.Why is post-order traversal used instead of pre-order traversal for this problem?

3.If a node's left subtree has max value 50 and right subtree has min value 60, for what value of root is the combined tree a valid BST?

Back to DSA Sheet