Merge two binary trees

Tree Depth-First Search Breadth-First Search Binary Tree

79.0% acceptance

Feb 20, 2026

9065

322

You are given two binary trees root1 and root2. Merge them into a new tree. If two nodes overlap, sum their values; otherwise use the non-null node.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn merge_trees(
    root1: Option<Rc<RefCell<TreeNode>>>,
    root2: Option<Rc<RefCell<TreeNode>>>,
  ) -> Option<Rc<RefCell<TreeNode>>> {
    match (root1, root2) {
      (None, None) => None,
      (Some(n), None) | (None, Some(n)) => Some(n),
      (Some(n1), Some(n2)) => {
        let (l1, r1, v1) = {
          let b = n1.borrow();
          (b.left.clone(), b.right.clone(), b.val)
        };
        let (l2, r2, v2) = {
          let b = n2.borrow();
          (b.left.clone(), b.right.clone(), b.val)
        };
        let node = Rc::new(RefCell::new(TreeNode::new(v1 + v2)));
        node.borrow_mut().left = Solution::merge_trees(l1, l2);
        node.borrow_mut().right = Solution::merge_trees(r1, r2);
        Some(node)
      }
    }
  }
}