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.

Description Hints 1 Solution Video 28:09

333. Largest BST Subtree

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.

Medium45.8% acceptance2 companiesPremium elsewhere, free here

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?

Asked at 2 companies

Microsoft Meta

Topics

Hints open one at a time

Hint 1

You can recursively use algorithm similar to 98. Validate Binary Search Tree at each node of the tree, which will result in O(nlogn) time complexity.

28:09

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[10,5,15,1,8,null,7]

Input

[4,2,7,2,3,5,null,2,null,null,null,null,null,1]

Your code is saved on this device.Solution