Largest BST Subtree - Solution & Explanation

Q: Is Largest BST Subtree easy or hard?

Largest BST Subtree is generally rated Medium on coding platforms. The difficulty comes from combining BST validation with subtree aggregation in a single traversal. Once the idea of returning metadata from each DFS call is understood, the implementation becomes straightforward.

Q: Largest BST Subtree Python/Java solution

Most implementations use a recursive DFS function that returns a tuple or object containing isBST, size, min, and max values. Python typically returns a tuple, while Java and C++ often use a custom class or struct. The logic remains the same across languages and runs in O(n) time.

Q: How to solve Largest BST Subtree in O(n)?

Use a postorder depth-first traversal that returns four values for each subtree: whether it is a BST, the subtree size, the minimum value, and the maximum value. If both children are BSTs and their values satisfy left.max < node.val < right.min, the current subtree forms a BST. Update the size and propagate boundaries upward while tracking the largest size globally.

Q: What is the best approach for Largest BST Subtree?

The best approach is a postorder DFS that returns subtree metadata: whether the subtree is a BST, its size, and its min and max values. Each node combines results from its left and right children to determine if it forms a valid BST. This processes every node once, giving O(n) time complexity and O(h) recursion space.

Q: Is Largest BST Subtree asked at Google/Amazon/Meta?

Largest BST Subtree and similar tree-validation problems frequently appear in interviews at companies like Google, Amazon, and Meta. They test understanding of binary search tree properties, recursive traversal, and bottom-up reasoning on trees.

Q: What data structure is used in Largest BST Subtree?

The problem uses a binary tree as the primary data structure. The optimal algorithm relies on depth-first search recursion and tracks metadata such as subtree minimum, maximum, and size to verify Binary Search Tree properties.

Q: What is the time complexity of Largest BST Subtree?

The optimal solution runs in O(n) time because each node in the binary tree is visited exactly once during a postorder traversal. The brute force method that validates every subtree can take O(n^2) time in the worst case. Space complexity for the optimal approach is O(h), where h is the height of the tree.

MediumPremiumFree on FleetCodeDynamic Programming Tree Depth-First Search Binary Search Tree6 min readAsked at: Microsoft, Meta

Practice this problem

Problem Statement

Given the root of a binary tree, find the largest subtree, which is also a Binary Search Tree (BST), where the largest means subtree has the largest number of nodes.

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties:

The left subtree values are less than the value of their parent (root) node's value.
The right subtree values are greater than the value of their parent (root) node's value.

Note: A subtree must include all of its descendants.

Example 1:

Input: root = [10,5,15,1,8,null,7]
Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.

Example 2:

Input: root = [4,2,7,2,3,5,null,2,null,null,null,null,null,1]
Output: 2

Constraints:

The number of nodes in the tree is in the range [0, 10⁴].
-10⁴ <= Node.val <= 10⁴

Follow up: Can you figure out ways to solve it with O(n) time complexity?

Approach Overview

Problem Overview: You are given a binary tree that is not necessarily a binary search tree. The task is to find the size (number of nodes) of the largest subtree that satisfies the Binary Search Tree property. A subtree counts only if every node inside it follows the BST rule: left values are smaller and right values are larger.

Approach 1: Validate Every Subtree (Brute Force) (Time: O(n^2), Space: O(h))

The direct idea is to treat every node as the root of a potential BST. For each node, run a validation check to confirm whether the subtree rooted at that node satisfies BST rules. The validation function recursively ensures left < root < right while computing the subtree size. If the subtree is valid, update the global maximum size. Because each validation may traverse many nodes repeatedly, the worst-case complexity becomes O(n^2) when the tree is skewed. Space complexity is O(h) due to recursion depth. This approach is straightforward but inefficient for large trees.

Approach 2: Postorder DFS with Subtree Metadata (Optimal) (Time: O(n), Space: O(h))

The optimal solution uses a single postorder traversal from the leaves upward. Each DFS call returns metadata about the current subtree: whether it forms a BST, its size, and the minimum and maximum values inside it. While returning from recursion, you combine the results from the left and right children. A subtree is a valid BST if the left and right subtrees are BSTs and left.max < node.val < right.min. When this condition holds, the subtree size becomes left.size + right.size + 1, and the min/max boundaries are updated accordingly.

If the condition fails, the subtree is marked invalid so its parent cannot treat it as part of a BST. During traversal you maintain a global maximum representing the largest valid BST encountered so far. Each node is processed exactly once, giving O(n) time complexity and O(h) space for recursion. This technique is a classic combination of Depth-First Search and bottom-up state aggregation similar to Dynamic Programming on trees.

The key insight is that every subtree can summarize enough information (min, max, size, validity) for its parent to make a constant-time decision. This avoids repeatedly scanning subtrees. The pattern appears frequently in binary tree problems where parent decisions depend on child properties.

Recommended for interviews: The postorder DFS solution is what interviewers expect. Mentioning the brute force approach first demonstrates understanding of the problem structure. Transitioning to the single-pass postorder solution shows optimization skills and familiarity with bottom-up tree processing.

Solution

Code

Python Java C++Go

Python

Java

C++

Try this approach in the editor →

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Validate Each Subtree (Brute Force)	O(n^2)	O(h)	Good for understanding the problem and small trees where repeated validation cost is acceptable
Postorder DFS with Min/Max Tracking	O(n)	O(h)	Best general solution. Processes each node once and scales well for large trees

Video Solution

Largest BST Subtree - Solution | Binary Trees | Data Structure and Algorithms in JAVA • Pepcoding • 22,887 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Largest BST Subtree easy or hard?

Largest BST Subtree is generally rated Medium on coding platforms. The difficulty comes from combining BST validation with subtree aggregation in a single traversal. Once the idea of returning metadata from each DFS call is understood, the implementation becomes straightforward.

Largest BST Subtree Python/Java solution

Most implementations use a recursive DFS function that returns a tuple or object containing isBST, size, min, and max values. Python typically returns a tuple, while Java and C++ often use a custom class or struct. The logic remains the same across languages and runs in O(n) time.

How to solve Largest BST Subtree in O(n)?

Use a postorder depth-first traversal that returns four values for each subtree: whether it is a BST, the subtree size, the minimum value, and the maximum value. If both children are BSTs and their values satisfy left.max < node.val < right.min, the current subtree forms a BST. Update the size and propagate boundaries upward while tracking the largest size globally.

What is the best approach for Largest BST Subtree?

The best approach is a postorder DFS that returns subtree metadata: whether the subtree is a BST, its size, and its min and max values. Each node combines results from its left and right children to determine if it forms a valid BST. This processes every node once, giving O(n) time complexity and O(h) recursion space.

Is Largest BST Subtree asked at Google/Amazon/Meta?

Largest BST Subtree and similar tree-validation problems frequently appear in interviews at companies like Google, Amazon, and Meta. They test understanding of binary search tree properties, recursive traversal, and bottom-up reasoning on trees.

What data structure is used in Largest BST Subtree?

The problem uses a binary tree as the primary data structure. The optimal algorithm relies on depth-first search recursion and tracks metadata such as subtree minimum, maximum, and size to verify Binary Search Tree properties.

What is the time complexity of Largest BST Subtree?

The optimal solution runs in O(n) time because each node in the binary tree is visited exactly once during a postorder traversal. The brute force method that validates every subtree can take O(n^2) time in the worst case. Space complexity for the optimal approach is O(h), where h is the height of the tree.

Ready to solve this problem?

Practice Largest BST Subtree with our built-in code editor and test cases.

Practice on FleetCode

Longest Palindromic Substring

Regular Expression Matching

Problem Info

DifficultyMedium

Acceptance45.8%

Approaches1

Reading time6 min

Asked at

Microsoft Meta