Maximum sum bst in binary tree

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

46.5% acceptance

Feb 25, 2026

2966

198

Given a binary tree root, return the maximum sum of all keys of any sub-tree which is also a Binary Search Tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_sum_bst(root: Option<std::rc::Rc<std::cell::RefCell<crate::TreeNode>>>) -> i32 {
    // Returns (is_bst, min_val, max_val, sum) for the subtree
    let mut ans = 0i32;
    fn dfs(node: Option<std::rc::Rc<std::cell::RefCell<crate::TreeNode>>>, ans: &mut i32) -> (bool, i32, i32, i32) {
      match node {
        None => (true, i32::MAX, i32::MIN, 0),
        Some(n) => {
          let n = n.borrow();
          let (lb, lmin, lmax, lsum) = dfs(n.left.clone(), ans);
          let (rb, rmin, rmax, rsum) = dfs(n.right.clone(), ans);
          let v = n.val;
          if lb && rb && lmax < v && v < rmin {
            let sum = lsum + rsum + v;
            *ans = (*ans).max(sum);
            (true, lmin.min(v), rmax.max(v), sum)
          } else {
            (false, i32::MIN, i32::MAX, 0)
          }
        }
      }
    }
    dfs(root, &mut ans);
    ans
  }
}