Construct binary tree from preorder and inorder traversal

Array Hash Table Divide and Conquer Tree Binary Tree

68.4% acceptance

Feb 27, 2026

16551

625

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

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 build_tree_preorder_inorder(preorder: Vec<i32>, inorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
    if preorder.is_empty() {
      return None;
    }
    
    fn build(preorder: &[i32], inorder: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
      if preorder.is_empty() {
        return None;
      }
      
      let root_val = preorder[0];
      let root_idx = inorder.iter().position(|&x| x == root_val).unwrap();
      
      let left = build(&preorder[1..root_idx + 1], &inorder[..root_idx]);
      let right = build(&preorder[root_idx + 1..], &inorder[root_idx + 1..]);
      
      Some(Rc::new(RefCell::new(TreeNode {
        val: root_val,
        left,
        right,
      })))
    }
    
    build(&preorder, &inorder)
  }
}