On this page

Largest Bst in Binary Tree

Given a binary tree, find the size of the largest subtree that is a valid BST (the subtree must include all descendants of its root). The size is the number of nodes.

A whole tree that is a BST counts, and a single node is always a BST of size 1.

Intuition

1 10
2 / \
3 5 15
4 / \ \
5 1 8 7

The subtree rooted at 5 (nodes 5, 1, 8) is a BST of size 3. The subtree rooted at 15 is not a BST because 7 is in its right subtree but is smaller than 15. The whole tree is not a BST either. The answer is 3.

For each node, a subtree is a BST if its left and right subtrees are both BSTs, the largest value on the left is smaller than the node, and the smallest value on the right is larger than the node. So each subtree needs to report three facts to its parent: its minimum, its maximum, and its size (when it is a BST).

This is a postorder idea: the answer for a node is built from the answers of its children.

Approach: Return (min, max, size) Bottom-Up

Write solve(node) that returns a triple (min, max, size):

  1. Empty tree: return (+infinity, -infinity, 0). These bounds make an empty side never block the checks below.
  2. Get left = solve(node.left) and right = solve(node.right).
  3. If left.max < node.data < right.min, this whole subtree is a BST:
    • min = min(node.data, left.min)
    • max = max(node.data, right.max)
    • size = left.size + right.size + 1
  4. Otherwise it is not a BST. Return (-infinity, +infinity, max(left.size, right.size)). The impossible bounds guarantee that no ancestor can accept this subtree as part of a BST, while the size still carries the best BST found below.
  5. The answer is solve(root).size.

At every node, size is either the size of the BST rooted here or the largest BST found anywhere in its subtree, so the root's size is the final answer.

Code

class Solution {
struct Info {
int mn, mx, size;
};
Info solve(Node* node) {
if (node == nullptr) return {INT_MAX, INT_MIN, 0};
Info left = solve(node->left);
Info right = solve(node->right);
if (node->data > left.mx && node->data < right.mn) {
return {min(node->data, left.mn),
max(node->data, right.mx),
left.size + right.size + 1};
}
return {INT_MIN, INT_MAX, max(left.size, right.size)};
}
public:
int largestBst(Node* root) {
return solve(root).size;
}
};

Complexity

Time: O(n)

Each node is visited once and does constant work. The brute force, validating a BST at every node, is O(n^2).

Space: O(h)

Recursion stack depth equals the tree height.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"The brute force checks whether each subtree is a BST, which is O of n squared. Instead I go bottom up in postorder, and each subtree returns three things: its minimum, its maximum and its size. An empty tree returns plus infinity, minus infinity and zero so it never blocks a check. At a node, if the max of the left side is smaller than the node and the min of the right side is larger, the subtree is a BST, so I return the combined min and max and the size left plus right plus one. If not, I return a minimum of minus infinity and a maximum of plus infinity, so no ancestor can accept it, along with the larger child size, which keeps the best BST found so far. The answer is the size at the root. Time is O of n and space is O of h."
Next TopicSearch in a Tree