Start learning free

LESSON 424 OF 543 · BINARY TREES

Construct Binary Tree from Preorder and Inorder in Rust: O(n)

Practice O(n) Read the full explanation

Two arrays describe the same binary tree:

  • preorder lists the values in preorder: first a node, then its whole left subtree, then its whole right subtree.
  • inorder lists the values in inorder: first a node's whole left subtree, then the node, then its whole right subtree.

All the values are different. Build the tree and return its root.

The tests print the tree you return level by level, from left to right, with null where a child is missing and the trailing nulls left out. For example, [1,2,null,3] is the tree with root 1, 2 as its left child and 3 as the left child of 2.

 

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
    3
   / \
  9   20
     /  \
    15   7

Explanation: preorder starts with 3, so 3 is the root. In inorder, 9 is left of 3 and 15, 20, 7 are right of it: 9 is the left subtree and 15, 20, 7 are the right subtree. The right subtree's values come next in preorder, starting with 20, its root; in inorder 15 is left of 20 and 7 is right of it.

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]
Explanation: A single value is a tree with only a root.

Example 3:

Input: preorder = [1,2,3], inorder = [3,2,1]
Output: [1,2,null,3]
      1
     /
    2
   /
  3

Explanation: In inorder, every value comes before its parent, so each node has only a left child. The same preorder with inorder = [1,2,3] would give a line going right: [1,null,2,null,3].

 

Constraints:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • Every value is between -3000 and 3000, and the values are all different.
  • preorder and inorder are the preorder and inorder traversals of the same tree.
  • The tree is at most 400 levels deep.

Note:

The solution should run in O(n) time, where n is the number of values: build each node once, and find where a value sits in inorder with a HashMap instead of a search.

STEP 1 OF 13
    Ctrl + Enter to check

    RUST · BINARY TREES

    Construct Binary Tree From Preorder And Inorder Traversal in Rust, explained

    Problem overview

    build_tree receives two vectors, preorder and inorder, which are the preorder and inorder traversals of the same binary tree. All values are different. The function returns the root of that tree as an Option<Box<TreeNode>>. The lesson provides TreeNode, with the fields val, left and right, and TreeNode::new(val), which makes a node with no children.

    Preorder visits a node, then its whole left subtree, then its whole right subtree. Inorder visits the left subtree, then the node, then the right subtree.

    For preorder = [3,9,20,15,7] and inorder = [9,3,15,20,7] the answer is the tree [3,9,20,null,null,15,7]: 3 is the root, 9 its left child, and 20 its right child with the children 15 and 7.

    Approach: the first preorder value is always a root

    Preorder tells you which value is the root of any subtree: it comes first. Inorder tells you what is on each side of it: once you find the root in inorder, everything to its left belongs to the left subtree and everything to its right belongs to the right subtree.

    In the example, the first preorder value is 3. In inorder it sits at index 1, so [9] is the left subtree and [15,20,7] the right one. The next preorder value, 9, is the root of the left subtree. The left subtree has no more values, so the next value, 20, is the root of the right subtree, and the same reasoning applies again.

    That gives a recursion over ranges of inorder. Every subtree fills one unbroken stretch of it, so two indexes, lo and hi, describe the subtree. A global counter into preorder hands out the roots in the order the recursion needs them: a node's root first, then every root of its left subtree, then every root of its right subtree. That is exactly preorder, so the counter only moves forward.

    The note asks for O(n) time. Scanning inorder to find each root would cost O(n) per node, O(n²) in total for a skewed tree. A HashMap from each value to its inorder index makes each lookup constant. It works because the values are all different.

    Step by step

    1. Create inorder_index as an empty HashMap. Rust infers the key and value types from the first insert.
    2. Loop over inorder.iter().enumerate(), which yields each index i with a reference to its value.
    3. Insert *value with i as i32. The * reads the number behind the reference. The index is an i32 because the helper's ranges can end at -1 when they are empty.
    4. Create pre_index as let mut, starting at 0: the position in preorder of the next root.
    5. End build_tree with the helper's result. It gets the preorder slice, the map, a mutable borrow of the counter, and the whole inorder range, 0 to inorder.len() as i32 - 1.
    6. Declare build with the slice, the map, the counter as &mut usize, and lo and hi. Lending the counter mutably lets every call advance the same one.
    7. Return None when lo > hi. An empty range holds no values, so there is no tree. This stops the recursion below every leaf.
    8. Take the next root as preorder[*pre_index], then add 1 to *pre_index.
    9. Create the node with Box::new(TreeNode::new(value)), declared mut because its children are assigned next.
    10. Find the root in inorder with inorder_index[&value], in mid.
    11. Build the left subtree from the range lo to mid - 1 and store it in node.left. The left call must come first, because its roots come right after this node in preorder.
    12. Build the right subtree from mid + 1 to hi. The left call has used all of its roots, so the counter now points at the right subtree's root.
    13. Return Some(node) without a semicolon.

    The solution in Rust

    use std::collections::HashMap;

impl Solution {
    fn build(preorder: &[i32], inorder_index: &HashMap<i32, i32>, pre_index: &mut usize, lo: i32, hi: i32) -> Option<Box<TreeNode>> {
        if lo > hi {
            return None;
        }
        let value = preorder[*pre_index];
        *pre_index += 1;
        let mut node = Box::new(TreeNode::new(value));
        let mid = inorder_index[&value];
        node.left = Self::build(preorder, inorder_index, pre_index, lo, mid - 1);
        node.right = Self::build(preorder, inorder_index, pre_index, mid + 1, hi);
        Some(node)
    }

    fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> Option<Box<TreeNode>> {
        let mut inorder_index = HashMap::new();
        for (i, value) in inorder.iter().enumerate() {
            inorder_index.insert(*value, i as i32);
        }
        let mut pre_index = 0;
        Self::build(&preorder, &inorder_index, &mut pre_index, 0, inorder.len() as i32 - 1)
    }
}

    Rust details worth a closer look:

    • The shared counter. pre_index: &mut usize is a mutable borrow. Inside build, *pre_index reads and writes the number it points to. Passing pre_index into the recursive calls hands the same borrow on; Rust reborrows it for each call, so both calls can use it one after the other.
    • &preorder as a slice. build_tree owns a Vec<i32>, and &preorder coerces to the &[i32] that build asks for.
    • Indexing a map. inorder_index[&value] panics if the key is missing. That can't happen when the two inputs describe the same tree.
    • i32 and usize. The map and the range bounds use i32, since mid - 1 can be -1. The counter is a usize because it indexes preorder. With lo and hi as usize, mid - 1 would underflow when mid is 0.
    • Moving the node. Some(node) moves the box into the Option. That's why the children are set before it: after the move, node can no longer be used.
    • The use line. HashMap lives in std::collections, so the solution begins with use std::collections::HashMap;.

    Complexity

    Time: O(n). Filling the map takes one pass over inorder. After that, each call of build that isn't empty creates exactly one node and does one constant-time map lookup, and there are n such calls plus at most n + 1 empty ones.

    Space: O(n). The map holds n entries, and the tree has n nodes. The recursion goes as deep as the tree, at most 400 levels in this lesson.

    Edge cases and common mistakes

    • One value. [-1] and [-1] give a tree with only a root. The left range is 0..=-1 and the right one is 1..=0, both empty.
    • Building the right subtree first. The counter would hand the left subtree's roots to the right side. The two calls must follow preorder's order: left, then right.
    • Left-only and right-only chains. preorder = [1,2,3] with inorder = [3,2,1] gives [1,2,null,3], because every value comes before its parent in inorder. With inorder = [1,2,3] the result is [1,null,2,null,3].
    • Searching instead of mapping. A linear search for value in inorder works, but costs O(n²) on a chain.
    • Duplicates. The map and the whole idea rest on values being different. With repeats, one value could have two positions and the split would be ambiguous.
    • Forgetting as i32. Inserting the usize index makes the map a HashMap<i32, usize>, and passing it to build, which expects &HashMap<i32, i32>, is a type error.

    Testing

    Printed level by level, as the lesson does, the reference solution gives:

    • preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] gives [3,9,20,null,null,15,7].
    • preorder = [-1], inorder = [-1] gives [-1].
    • preorder = [1,2,3], inorder = [3,2,1] gives [1,2,null,3].
    • preorder = [1,2,3], inorder = [1,2,3] gives [1,null,2,null,3].
    • preorder = [1,2,3], inorder = [2,1,3] gives [1,2,3].
    • preorder = [1,2,4,5,3], inorder = [4,2,5,1,3] gives [1,2,3,4,5].
    Keep going with Rust500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free