Largest BST in a Binary Tree Hard 0 attempts
GeeksforGeeks ↗

Largest BST in a Binary Tree

Hard TreeBinary TreeDFS GeeksforGeeks

Given a binary tree, find the size (number of nodes) of the largest subtree which is also a valid Binary Search Tree (BST). A BST is a tree where for every node, all values in the left subtree are smaller and all values in the right subtree are larger.

Example:

Input: root = [10,5,15,1,8,null,7]
Output: 3 (the subtree rooted at 5 with nodes {1, 5, 8})
Sample Input
—
Sample Output
—
Constraints
  • 1 <= N <= 10^5
  • 1 <= Node.val <= 10^6
Test Cases
Case 1
Args: [[10,5,15,1,8,null,7]] Expected: 3
Topics
TreeBinary TreeDFS

Approach: Postorder Traversal

For each node, return its subtree size, min, max, and whether it is a valid BST. A node forms a valid BST if both children are BSTs and the node value is within the valid range. Track the maximum BST size found.

function largestBstInABinaryTree(root) {
  let maxSize = 0;
  function solve(node) {
    if (!node) return { size: 0, min: Infinity, max: -Infinity, isBST: true };
    const left = solve(node.left);
    const right = solve(node.right);
    if (left.isBST && right.isBST && node.val > left.max && node.val < right.min) {
      const size = left.size + right.size + 1;
      maxSize = Math.max(maxSize, size);
      return { size, min: Math.min(node.val, left.min), max: Math.max(node.val, right.max), isBST: true };
    }
    return { size: 0, min: 0, max: 0, isBST: false };
  }
  solve(root);
  return maxSize;
}

Time Complexity: O(n)

Space Complexity: O(h)

Saved in this browser only. Private to you.

JavaScript