All elements in two binary search trees

Tree Depth-First Search Binary Search Tree Sorting Binary Tree

80.2% acceptance

Feb 27, 2026

3186

Given two binary search trees root1 and root2, return a list containing all the integers from both trees sorted in ascending order.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn get_all_elements(root1: Option<Rc<RefCell<TreeNode>>>, root2: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    let mut a = Vec::new();
    let mut b = Vec::new();
    Self::inorder(root1, &mut a);
    Self::inorder(root2, &mut b);
    // merge two sorted arrays
    let (mut i, mut j) = (0, 0);
    let mut res = Vec::with_capacity(a.len() + b.len());
    while i < a.len() && j < b.len() {
      if a[i] <= b[j] { res.push(a[i]); i += 1; }
      else { res.push(b[j]); j += 1; }
    }
    while i < a.len() { res.push(a[i]); i += 1; }
    while j < b.len() { res.push(b[j]); j += 1; }
    res
  }

  fn inorder(node: Option<Rc<RefCell<TreeNode>>>, out: &mut Vec<i32>) {
    if let Some(n) = node {
      let b = n.borrow();
      Self::inorder(b.left.clone(), out);
      out.push(b.val);
      Self::inorder(b.right.clone(), out);
    }
  }
}