Merge bsts to create single bst

Array Hash Table Tree Depth-First Search Binary Search Tree Binary Tree

38.0% acceptance

Feb 25, 2026

657

You are given n BST (binary search tree) root nodes for n separate BSTs stored in an array trees (0-indexed). Each BST in trees has at most 3 nodes, and no two roots have the same value. In one operation, you can: Select two distinct indices i and j such that the value stored at one of the leaves of trees[i] is equal to the root value of trees[j]. Replace the leaf node in trees[i] with trees[j]. Remove trees[j] from trees. Return the root of the resulting BST if it is possible to form a valid BST after performing n - 1 operations, or null if it is impossible to create a valid BST. A BST (binary search tree) is a binary tree where each node satisfies the following property: Every node in the node's left subtree has a value strictly less than the node's value. Every node in the node's right subtree has a value strictly greater than the node's value. A leaf is a node that has no children.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
use std::collections::{HashMap, HashSet};

impl Solution {
  pub fn can_merge(trees: Vec<Option<Rc<RefCell<TreeNode>>>>) -> Option<Rc<RefCell<TreeNode>>> {
    let mut root_map: HashMap<i32, Rc<RefCell<TreeNode>>> = HashMap::new();
    let mut root_vals: HashSet<i32> = HashSet::new();
    let mut leaf_count: HashMap<i32, i32> = HashMap::new();

    for tree in &trees {
      if let Some(node) = tree {
        let val = node.borrow().val;
        root_vals.insert(val);
        root_map.insert(val, Rc::clone(node));
      }
    }

    for tree in &trees {
      if let Some(node) = tree {
        let b = node.borrow();
        if let Some(ref left) = b.left {
          *leaf_count.entry(left.borrow().val).or_insert(0) += 1;
        }
        if let Some(ref right) = b.right {
          *leaf_count.entry(right.borrow().val).or_insert(0) += 1;
        }
      }
    }

    // Find the root: a root node whose value is not a leaf of any other tree
    let mut main_root = None;
    for &val in &root_vals {
      if !leaf_count.contains_key(&val) {
        if main_root.is_some() {
          return None; // multiple roots
        }
        main_root = Some(val);
      }
    }

    let main_root = main_root?;
    let root = root_map.remove(&main_root)?;

    // Build tree by merging
    Self::merge(&root, &mut root_map);

    // All trees should have been used
    if !root_map.is_empty() {
      return None;
    }

    // Validate BST
    if Self::is_valid_bst(&Some(Rc::clone(&root)), i64::MIN, i64::MAX) {
      Some(root)
    } else {
      None
    }
  }

  fn merge(node: &Rc<RefCell<TreeNode>>, root_map: &mut HashMap<i32, Rc<RefCell<TreeNode>>>) {
    let mut b = node.borrow_mut();

    // Try to merge left child
    if let Some(ref left) = b.left {
      let lv = left.borrow().val;
      if left.borrow().left.is_none() && left.borrow().right.is_none() {
        if let Some(subtree) = root_map.remove(&lv) {
          b.left = Some(Rc::clone(&subtree));
          Self::merge(&subtree, root_map);
        }
      }
    }

    // Try to merge right child
    if let Some(ref right) = b.right {
      let rv = right.borrow().val;
      if right.borrow().left.is_none() && right.borrow().right.is_none() {
        if let Some(subtree) = root_map.remove(&rv) {
          b.right = Some(Rc::clone(&subtree));
          Self::merge(&subtree, root_map);
        }
      }
    }
  }

  fn is_valid_bst(node: &Option<Rc<RefCell<TreeNode>>>, min: i64, max: i64) -> bool {
    match node {
      None => true,
      Some(n) => {
        let b = n.borrow();
        let val = b.val as i64;
        if val <= min || val >= max {
          return false;
        }
        Self::is_valid_bst(&b.left, min, val) && Self::is_valid_bst(&b.right, val, max)
      }
    }
  }
}