Largest BST in a Binary Tree Hard 0 attempts
GeeksforGeeks ↗

Largest BST in a Binary Tree

Hard TreeBinary TreeDFS GeeksforGeeks

Somewhere inside a given binary tree, there may be a subtree that happens to satisfy the binary search tree property — every node's left descendants hold smaller values and its right descendants hold larger ones. Find the largest such subtree and report how many nodes it contains.

Input Format
Implement largestBstInABinaryTree(root). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
root = [10,5,15,1,8,null,7]
Output
3

Example 2

Input
root = [2,1,3]
Output
3
Constraints
  • 1 <= N <= 10^5
  • 1 <= Node.val <= 10^6
Test Cases (2)
Case 1
Args: [[10,5,15,1,8,null,7]] Expected: 3
Case 2
Args: [[2,1,3]] Expected: 3
Topics
TreeBinary TreeDFS

Iterative Postorder

Each subtree reports its size, minimum, maximum, and validity. A parent is a BST only if both children are BSTs and their value ranges lie strictly on the correct sides.

javascript
function largestBstInABinaryTree(root) {
  if (!root) return 0;
  const order = [], stack = [root];
  while(stack.length) {
    const node=stack.pop();order.push(node);
    if(node.left)stack.push(node.left);
    if(node.right)stack.push(node.right);
  }
  const info=new Map(),empty={size:0,min:Infinity,max:-Infinity,valid:true};let best=0;
  for(let i=order.length-1;i>=0;i--) {
    const node=order[i],l=info.get(node.left)||empty,r=info.get(node.right)||empty;
    if(l.valid&&r.valid&&node.val>l.max&&node.val<r.min) {
      const size=l.size+r.size+1;best=Math.max(best,size);
      info.set(node,{size,min:Math.min(node.val,l.min),max:Math.max(node.val,r.max),valid:true});
    } else info.set(node,{valid:false});
  }
  return best;
}

Time: O(n) | Space: O(n) auxiliary space, excluding output

Saved in this browser only. Private to you.

JavaScript