Largest bst subtree

Dynamic Programming Tree Depth-First Search Binary Search Tree Binary Tree

45.8% acceptance

Mar 31, 2026

1567

148

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn largest_bst_subtree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    // Returns (is_bst, size, min, max)
    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, ans: &mut i32) -> (bool, i32, i32, i32) {
      match node {
        None => (true, 0, i32::MAX, i32::MIN),
        Some(n) => {
          let n = n.borrow();
          let (lb, ls, lmin, lmax) = dfs(&n.left, ans);
          let (rb, rs, rmin, rmax) = dfs(&n.right, ans);
          if lb && rb && lmax < n.val && n.val < rmin {
            let size = ls + rs + 1;
            *ans = (*ans).max(size);
            (true, size, lmin.min(n.val), rmax.max(n.val))
          } else {
            (false, 0, 0, 0)
          }
        }
      }
    }
    let mut ans = 0;
    dfs(&root, &mut ans);
    ans
  }
}