Construct Binary Tree from Preorder and Inorder Traversal

Problem Statement

Given two integer arrays preorder and inorder where:

• preorder is the preorder traversal of a binary tree
• inorder is the inorder traversal of the same tree

Reconstruct and return the binary tree.

Preorder traversal visits nodes in this order: Root → Left → Right

Inorder traversal visits nodes in this order: Left → Root → Right

What to notice first

• The first element in preorder is always the root of the current subtree.
• Once you identify the root in inorder, everything left of it is in the left subtree, and everything right of it is in the right subtree.
• This divide-and-conquer property allows you to recursively build left and right subtrees.
• Preorder has the root first, so you process elements from preorder in order, and use inorder to partition the tree.

Examples

Preorder	Inorder	Tree Structure
[3, 9, 20, 15, 7]	[9, 3, 15, 20, 7]	Root=3, Left child=9, Right child=20 (with its own subtree)
[1]	[1]	Single node tree
[1, 2, 3]	[1, 3, 2]	Root=1, Right child=2, Left child of 2 is 3

Constraints

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder and inorder consist of unique values.
• Each value of preorder also appears in inorder.
• inorder does not contain duplicates.
• preorder does not contain duplicates.

Real-World Applications

Where this pattern appears

• Serialization/Deserialization — Reconstructing objects from multiple views of a data structure.
• Compiler AST Construction — Building abstract syntax trees from tokenized source code.
• File System Traversal Logs — Reconstructing directory hierarchies from traversal records.
• Network Topology Recovery — Rebuilding network trees from different traversal snapshots.
• Expression Tree Building — Constructing operator trees from infix and prefix notations.

Complexity Comparison

Approach	Time	Space	Lookup	Best When
Hash Map	O(n)	O(n)	Instant O(1)	General case — predictable performance
Index Tracking	O(n²) worst	O(h)	O(n) linear search	Memory-constrained, or when inorder lookups are rare
Iterative with Stack	O(n)	O(h)	Instant O(1)	Advanced optimization

Which approach should you learn first?

• Pick Hash Map if you want the clearest, most balanced approach.
• Pick Index Tracking if you want to minimize extra space and understand the basic recursion pattern.

Best for Speed

Hash Map

O(n) time · O(n) space

Space-Efficient

Index Tracking

O(n²) worst · O(h) space

Approach 1: Hash Map (Recommended)

★ Recommended

Store the position of each value in inorder in a hash map for instant lookup. For each node in preorder, find its position in inorder to determine the split between left and right subtrees.

The key insight: once you know the root (from preorder), you can instantly find its position in inorder using the hash map, then partition the arrays and recurse.

⏱ Time O(n) Single pass per element 💾 Space O(n) Hash map + recursion stack

Step-by-step Example

Preorder: [3, 9, 20, 15, 7]

Inorder: [9, 3, 15, 20, 7]

Hash Map: {9: 0, 3: 1, 15: 2, 20: 3, 7: 4}

Step	Root	Position in Inorder	Left Elements	Right Elements	Action
1	3 (preorder[0])	1	[9] at inorder[0:1]	[15, 20, 7] at inorder[2:5]	Split at position 1
2	9 (preorder[1])	0	[]	[]	Leaf node
3	20 (preorder[2])	3	[15] at inorder[2:3]	[7] at inorder[4:5]	Split at position 3

Animated walkthrough

How the reconstruction algorithm finds the tree structure

Watch as the preorder root pointer moves forward and the inorder boundaries shrink during recursion.

Back Autoplay Next Reset

Step 1 of 3 Target: root

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function buildTreeHashMap(preorder, inorder):
    if preorder is empty or inorder is empty:
        return null

    // Create hash map for O(1) lookup
    inorder_map = {}
    for i, val in enumerate(inorder):
        inorder_map[val] = i

    function build(preorder_start, preorder_end, inorder_start, inorder_end):
        if preorder_start > preorder_end or inorder_start > inorder_end:
            return null

        root_val = preorder[preorder_start]
        root = new TreeNode(root_val)

        // Find root position in inorder
        root_inorder_idx = inorder_map[root_val]

        // Calculate left subtree size
        left_size = root_inorder_idx - inorder_start

        // Recurse on left subtree
        root.left = build(
            preorder_start + 1,
            preorder_start + left_size,
            inorder_start,
            root_inorder_idx - 1
        )

        // Recurse on right subtree
        root.right = build(
            preorder_start + left_size + 1,
            preorder_end,
            root_inorder_idx + 1,
            inorder_end
        )

        return root

    return build(0, len(preorder) - 1, 0, len(inorder) - 1)

Solution Code

Python

construct_binary_tree_from_preorder_and_inorder_traversal_hash_map.py

from typing import Optional, List, Dict


class TreeNode:
    def __init__(self, val: int = 0, left: Optional['TreeNode'] = None, right: Optional['TreeNode'] = None):
        self.val = val
        self.left = left
        self.right = right


def buildTree_hash_map(preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    """
    Construct a binary tree from preorder and inorder traversal using hash map.
    Time: O(n), Space: O(n)
    """
    if not preorder or not inorder:
        return None

    # Create a map for quick lookup of indices in inorder
    inorder_map: Dict[int, int] = {val: i for i, val in enumerate(inorder)}

    def build(preorder_start: int, preorder_end: int, inorder_start: int, inorder_end: int) -> Optional[TreeNode]:
        if preorder_start > preorder_end or inorder_start > inorder_end:
            return None

        # Root is the first element in preorder
        root_val = preorder[preorder_start]
        root = TreeNode(root_val)

        # Find root position in inorder
        root_inorder_idx = inorder_map[root_val]

        # Number of elements in left subtree
        left_size = root_inorder_idx - inorder_start

        # Build left subtree from remaining preorder and inorder
        root.left = build(
            preorder_start + 1,
            preorder_start + left_size,
            inorder_start,
            root_inorder_idx - 1
        )

        # Build right subtree
        root.right = build(
            preorder_start + left_size + 1,
            preorder_end,
            root_inorder_idx + 1,
            inorder_end
        )

        return root

    return build(0, len(preorder) - 1, 0, len(inorder) - 1)


# Test cases
if __name__ == "__main__":
    # Test 1: [3,9,20,15,7], [9,3,15,20,7]
    preorder1 = [3, 9, 20, 15, 7]
    inorder1 = [9, 3, 15, 20, 7]
    root1 = buildTree_hash_map(preorder1, inorder1)
    print(f"Test 1 - Root: {root1.val}")  # 3

    # Test 2: [1], [1]
    preorder2 = [1]
    inorder2 = [1]
    root2 = buildTree_hash_map(preorder2, inorder2)
    print(f"Test 2 - Root: {root2.val}")  # 1

    # Test 3: [1,2,3], [1,3,2]
    preorder3 = [1, 2, 3]
    inorder3 = [1, 3, 2]
    root3 = buildTree_hash_map(preorder3, inorder3)
    print(f"Test 3 - Root: {root3.val}, Left: {root3.left.val}, Right: {root3.right.val}")  # 1, 2, 3

C++

construct_binary_tree_from_preorder_and_inorder_traversal_hash_map.cpp

#include <vector>
#include <unordered_map>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
private:
    unordered_map<int, int> inorder_map;

    TreeNode* build(vector<int>& preorder, int preorder_start, int preorder_end,
                    int inorder_start, int inorder_end) {
        if (preorder_start > preorder_end || inorder_start > inorder_end) {
            return nullptr;
        }

        // Root is the first element in preorder
        int root_val = preorder[preorder_start];
        TreeNode* root = new TreeNode(root_val);

        // Find root position in inorder
        int root_inorder_idx = inorder_map[root_val];

        // Number of elements in left subtree
        int left_size = root_inorder_idx - inorder_start;

        // Build left subtree
        root->left = build(preorder, preorder_start + 1, preorder_start + left_size,
                           inorder_start, root_inorder_idx - 1);

        // Build right subtree
        root->right = build(preorder, preorder_start + left_size + 1, preorder_end,
                            root_inorder_idx + 1, inorder_end);

        return root;
    }

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty() || inorder.empty()) {
            return nullptr;
        }

        // Create a map for quick lookup of indices in inorder
        for (int i = 0; i < inorder.size(); i++) {
            inorder_map[inorder[i]] = i;
        }

        return build(preorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }
};

// Test cases
int main() {
    Solution sol;

    // Test 1: [3,9,20,15,7], [9,3,15,20,7]
    vector<int> preorder1 = {3, 9, 20, 15, 7};
    vector<int> inorder1 = {9, 3, 15, 20, 7};
    TreeNode* root1 = sol.buildTree(preorder1, inorder1);
    printf("Test 1 - Root: %d\n", root1->val);  // 3

    // Test 2: [1], [1]
    vector<int> preorder2 = {1};
    vector<int> inorder2 = {1};
    TreeNode* root2 = sol.buildTree(preorder2, inorder2);
    printf("Test 2 - Root: %d\n", root2->val);  // 1

    return 0;
}

Java

construct_binary_tree_from_preorder_and_inorder_traversal_hash_map.java

import java.util.HashMap;
import java.util.Map;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    private Map<Integer, Integer> inorderMap;

    private TreeNode build(int[] preorder, int preorderStart, int preorderEnd,
                          int inorderStart, int inorderEnd) {
        if (preorderStart > preorderEnd || inorderStart > inorderEnd) {
            return null;
        }

        // Root is the first element in preorder
        int rootVal = preorder[preorderStart];
        TreeNode root = new TreeNode(rootVal);

        // Find root position in inorder
        int rootInorderIdx = inorderMap.get(rootVal);

        // Number of elements in left subtree
        int leftSize = rootInorderIdx - inorderStart;

        // Build left subtree
        root.left = build(preorder, preorderStart + 1, preorderStart + leftSize,
                         inorderStart, rootInorderIdx - 1);

        // Build right subtree
        root.right = build(preorder, preorderStart + leftSize + 1, preorderEnd,
                          rootInorderIdx + 1, inorderEnd);

        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) {
            return null;
        }

        // Create a map for quick lookup of indices in inorder
        inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }

        return build(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }
}

// Test cases
class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();

        // Test 1: [3,9,20,15,7], [9,3,15,20,7]
        int[] preorder1 = {3, 9, 20, 15, 7};
        int[] inorder1 = {9, 3, 15, 20, 7};
        TreeNode root1 = sol.buildTree(preorder1, inorder1);
        System.out.println("Test 1 - Root: " + root1.val);  // 3

        // Test 2: [1], [1]
        int[] preorder2 = {1};
        int[] inorder2 = {1};
        TreeNode root2 = sol.buildTree(preorder2, inorder2);
        System.out.println("Test 2 - Root: " + root2.val);  // 1
    }
}

JavaScript

construct_binary_tree_from_preorder_and_inorder_traversal_hash_map.js

/**
 * Definition for a binary tree node.
 */
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * Construct a binary tree from preorder and inorder traversal using hash map.
 * Time: O(n), Space: O(n)
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
function buildTree(preorder, inorder) {
    if (preorder.length === 0 || inorder.length === 0) {
        return null;
    }

    // Create a map for quick lookup of indices in inorder
    const inorderMap = new Map();
    for (let i = 0; i < inorder.length; i++) {
        inorderMap.set(inorder[i], i);
    }

    const build = (preorderStart, preorderEnd, inorderStart, inorderEnd) => {
        if (preorderStart > preorderEnd || inorderStart > inorderEnd) {
            return null;
        }

        // Root is the first element in preorder
        const rootVal = preorder[preorderStart];
        const root = new TreeNode(rootVal);

        // Find root position in inorder
        const rootInorderIdx = inorderMap.get(rootVal);

        // Number of elements in left subtree
        const leftSize = rootInorderIdx - inorderStart;

        // Build left subtree
        root.left = build(
            preorderStart + 1,
            preorderStart + leftSize,
            inorderStart,
            rootInorderIdx - 1
        );

        // Build right subtree
        root.right = build(
            preorderStart + leftSize + 1,
            preorderEnd,
            rootInorderIdx + 1,
            inorderEnd
        );

        return root;
    };

    return build(0, preorder.length - 1, 0, inorder.length - 1);
}

// Test cases
if (require.main === module) {
    // Test 1: [3,9,20,15,7], [9,3,15,20,7]
    const preorder1 = [3, 9, 20, 15, 7];
    const inorder1 = [9, 3, 15, 20, 7];
    const root1 = buildTree(preorder1, inorder1);
    console.log(`Test 1 - Root: ${root1.val}`);  // 3

    // Test 2: [1], [1]
    const preorder2 = [1];
    const inorder2 = [1];
    const root2 = buildTree(preorder2, inorder2);
    console.log(`Test 2 - Root: ${root2.val}`);  // 1
}

module.exports = buildTree;

Rust

construct_binary_tree_from_preorder_and_inorder_traversal_hash_map.rs

use std::collections::HashMap;
use std::cell::RefCell;
use std::rc::Rc;

#[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,
        }
    }
}

pub struct Solution;

impl Solution {
    pub fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        if preorder.is_empty() || inorder.is_empty() {
            return None;
        }

        // Create a map for quick lookup of indices in inorder
        let inorder_map: HashMap<i32, usize> = inorder
            .iter()
            .enumerate()
            .map(|(i, &val)| (val, i))
            .collect();

        fn build(
            preorder: &[i32],
            inorder: &[i32],
            preorder_start: usize,
            preorder_end: usize,
            inorder_start: usize,
            inorder_end: usize,
            inorder_map: &HashMap<i32, usize>,
        ) -> Option<Rc<RefCell<TreeNode>>> {
            if preorder_start > preorder_end || inorder_start > inorder_end {
                return None;
            }

            // Root is the first element in preorder
            let root_val = preorder[preorder_start];
            let mut root = TreeNode::new(root_val);

            // Find root position in inorder
            let root_inorder_idx = *inorder_map.get(&root_val)?;

            // Number of elements in left subtree
            let left_size = root_inorder_idx - inorder_start;

            // Build left subtree
            root.left = build(
                preorder,
                inorder,
                preorder_start + 1,
                preorder_start + left_size,
                inorder_start,
                root_inorder_idx.saturating_sub(1),
                inorder_map,
            );

            // Build right subtree
            root.right = build(
                preorder,
                inorder,
                preorder_start + left_size + 1,
                preorder_end,
                root_inorder_idx + 1,
                inorder_end,
                inorder_map,
            );

            Some(Rc::new(RefCell::new(root)))
        }

        build(
            &preorder,
            &inorder,
            0,
            preorder.len() - 1,
            0,
            inorder.len() - 1,
            &inorder_map,
        )
    }
}

fn main() {
    // Test 1: [3,9,20,15,7], [9,3,15,20,7]
    let preorder1 = vec![3, 9, 20, 15, 7];
    let inorder1 = vec![9, 3, 15, 20, 7];
    let root1 = Solution::build_tree(preorder1, inorder1);
    if let Some(node) = root1 {
        println!("Test 1 - Root: {}", node.borrow().val);  // 3
    }

    // Test 2: [1], [1]
    let preorder2 = vec![1];
    let inorder2 = vec![1];
    let root2 = Solution::build_tree(preorder2, inorder2);
    if let Some(node) = root2 {
        println!("Test 2 - Root: {}", node.borrow().val);  // 1
    }
}

Go

construct_binary_tree_from_preorder_and_inorder_traversal_hash_map.go

package main

/**
 * Definition for a binary tree node.
 */
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

func buildTree(preorder []int, inorder []int) *TreeNode {
  if len(preorder) == 0 || len(inorder) == 0 {
    return nil
  }

  // Create a map for quick lookup of indices in inorder
  inorderMap := make(map[int]int)
  for i, val := range inorder {
    inorderMap[val] = i
  }

  var build func(int, int, int, int) *TreeNode
  build = func(preorderStart, preorderEnd, inorderStart, inorderEnd int) *TreeNode {
    if preorderStart > preorderEnd || inorderStart > inorderEnd {
      return nil
    }

    // Root is the first element in preorder
    rootVal := preorder[preorderStart]
    root := &TreeNode{Val: rootVal}

    // Find root position in inorder
    rootInorderIdx := inorderMap[rootVal]

    // Number of elements in left subtree
    leftSize := rootInorderIdx - inorderStart

    // Build left subtree
    root.Left = build(
      preorderStart+1,
      preorderStart+leftSize,
      inorderStart,
      rootInorderIdx-1,
    )

    // Build right subtree
    root.Right = build(
      preorderStart+leftSize+1,
      preorderEnd,
      rootInorderIdx+1,
      inorderEnd,
    )

    return root
  }

  return build(0, len(preorder)-1, 0, len(inorder)-1)
}

func main() {
  // Test 1: [3,9,20,15,7], [9,3,15,20,7]
  preorder1 := []int{3, 9, 20, 15, 7}
  inorder1 := []int{9, 3, 15, 20, 7}
  root1 := buildTree(preorder1, inorder1)
  println("Test 1 - Root:", root1.Val)  // 3

  // Test 2: [1], [1]
  preorder2 := []int{1}
  inorder2 := []int{1}
  root2 := buildTree(preorder2, inorder2)
  println("Test 2 - Root:", root2.Val)  // 1
}

Approach 2: Index Tracking

🎯 Interview Favourite

Instead of storing a hash map, use a pointer to track the current position in preorder, and search for the root in inorder manually during each recursion. This saves the O(n) space used by the hash map, but trades it for slower inorder lookups.

This approach is useful when space is severely limited or when you want to demonstrate understanding of the core recursion pattern without relying on extra data structures.

Performance caveat

The linear search in inorder during each recursion can lead to O(n²) worst-case time complexity in unbalanced trees. Use the hash map approach unless space is critical.

⏱ Time O(n²) Linear inorder search per node 💾 Space O(h) Recursion stack height

Step-by-step Example

Preorder: [3, 9, 20, 15, 7]

Inorder: [9, 3, 15, 20, 7]

Preorder pointer: Advances left-to-right through preorder

Step	Preorder Pointer	Current Value	Inorder Boundaries	Action
1	0	3	[0:5] → find 3 at 1	Split: left [0:1], right [2:5]
2	1	9	[0:1] → find 9 at 0	Leaf node
3	2	20	[2:5] → find 20 at 3	Split: left [2:3], right [4:5]

Pseudocode

function buildTreeIndex(preorder, inorder):
    if preorder is empty or inorder is empty:
        return null

    preorder_idx = 0

    function build(inorder_start, inorder_end):
        if inorder_start > inorder_end or preorder_idx >= len(preorder):
            return null

        root_val = preorder[preorder_idx]
        preorder_idx++
        root = new TreeNode(root_val)

        // Find root position in inorder by linear search
        root_inorder_idx = search(inorder, root_val, inorder_start, inorder_end)

        // Recurse on left subtree
        root.left = build(inorder_start, root_inorder_idx - 1)

        // Recurse on right subtree
        root.right = build(root_inorder_idx + 1, inorder_end)

        return root

    return build(0, len(inorder) - 1)

Solution Code

Python

construct_binary_tree_from_preorder_and_inorder_traversal_index.py

from typing import Optional, List


class TreeNode:
    def __init__(self, val: int = 0, left: Optional['TreeNode'] = None, right: Optional['TreeNode'] = None):
        self.val = val
        self.left = left
        self.right = right


def buildTree_index(preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    """
    Construct a binary tree from preorder and inorder traversal using index tracking.
    Time: O(n), Space: O(h) where h is height (excluding output tree)
    """
    if not preorder or not inorder:
        return None

    self.preorder_idx = 0

    def build(inorder_start: int, inorder_end: int) -> Optional[TreeNode]:
        if inorder_start > inorder_end or self.preorder_idx >= len(preorder):
            return None

        # Root is the current element in preorder
        root_val = preorder[self.preorder_idx]
        self.preorder_idx += 1
        root = TreeNode(root_val)

        # Find root position in inorder
        root_inorder_idx = inorder.index(root_val, inorder_start, inorder_end + 1)

        # Build left subtree from inorder[inorder_start : root_inorder_idx]
        root.left = build(inorder_start, root_inorder_idx - 1)

        # Build right subtree from inorder[root_inorder_idx + 1 : inorder_end + 1]
        root.right = build(root_inorder_idx + 1, inorder_end)

        return root

    return build(0, len(inorder) - 1)


# Test cases
if __name__ == "__main__":
    # Test 1: [3,9,20,15,7], [9,3,15,20,7]
    preorder1 = [3, 9, 20, 15, 7]
    inorder1 = [9, 3, 15, 20, 7]
    root1 = buildTree_index(preorder1, inorder1)
    print(f"Test 1 - Root: {root1.val}")  # 3

    # Test 2: [1], [1]
    preorder2 = [1]
    inorder2 = [1]
    root2 = buildTree_index(preorder2, inorder2)
    print(f"Test 2 - Root: {root2.val}")  # 1

    # Test 3: [1,2,3], [1,3,2]
    preorder3 = [1, 2, 3]
    inorder3 = [1, 3, 2]
    root3 = buildTree_index(preorder3, inorder3)
    print(f"Test 3 - Root: {root3.val}, Left: {root3.left.val}, Right: {root3.right.val}")  # 1, 2, 3

C++

construct_binary_tree_from_preorder_and_inorder_traversal_index.cpp

#include <vector>
#include <algorithm>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
private:
    int preorder_idx;

    TreeNode* build(vector<int>& preorder, vector<int>& inorder,
                    int inorder_start, int inorder_end) {
        if (inorder_start > inorder_end || preorder_idx >= preorder.size()) {
            return nullptr;
        }

        // Root is the current element in preorder
        int root_val = preorder[preorder_idx];
        preorder_idx++;
        TreeNode* root = new TreeNode(root_val);

        // Find root position in inorder
        auto it = find(inorder.begin() + inorder_start, inorder.begin() + inorder_end + 1, root_val);
        int root_inorder_idx = distance(inorder.begin(), it);

        // Build left subtree
        root->left = build(preorder, inorder, inorder_start, root_inorder_idx - 1);

        // Build right subtree
        root->right = build(preorder, inorder, root_inorder_idx + 1, inorder_end);

        return root;
    }

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty() || inorder.empty()) {
            return nullptr;
        }

        preorder_idx = 0;
        return build(preorder, inorder, 0, inorder.size() - 1);
    }
};

// Test cases
int main() {
    Solution sol;

    // Test 1: [3,9,20,15,7], [9,3,15,20,7]
    vector<int> preorder1 = {3, 9, 20, 15, 7};
    vector<int> inorder1 = {9, 3, 15, 20, 7};
    TreeNode* root1 = sol.buildTree(preorder1, inorder1);
    printf("Test 1 - Root: %d\n", root1->val);  // 3

    // Test 2: [1], [1]
    vector<int> preorder2 = {1};
    vector<int> inorder2 = {1};
    TreeNode* root2 = sol.buildTree(preorder2, inorder2);
    printf("Test 2 - Root: %d\n", root2->val);  // 1

    return 0;
}

Java

construct_binary_tree_from_preorder_and_inorder_traversal_index.java

import java.util.Arrays;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    private int preorderIdx;

    private TreeNode build(int[] preorder, int[] inorder,
                          int inorderStart, int inorderEnd) {
        if (inorderStart > inorderEnd || preorderIdx >= preorder.length) {
            return null;
        }

        // Root is the current element in preorder
        int rootVal = preorder[preorderIdx];
        preorderIdx++;
        TreeNode root = new TreeNode(rootVal);

        // Find root position in inorder
        int rootInorderIdx = -1;
        for (int i = inorderStart; i <= inorderEnd; i++) {
            if (inorder[i] == rootVal) {
                rootInorderIdx = i;
                break;
            }
        }

        // Build left subtree
        root.left = build(preorder, inorder, inorderStart, rootInorderIdx - 1);

        // Build right subtree
        root.right = build(preorder, inorder, rootInorderIdx + 1, inorderEnd);

        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) {
            return null;
        }

        preorderIdx = 0;
        return build(preorder, inorder, 0, inorder.length - 1);
    }
}

// Test cases
class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();

        // Test 1: [3,9,20,15,7], [9,3,15,20,7]
        int[] preorder1 = {3, 9, 20, 15, 7};
        int[] inorder1 = {9, 3, 15, 20, 7};
        TreeNode root1 = sol.buildTree(preorder1, inorder1);
        System.out.println("Test 1 - Root: " + root1.val);  // 3

        // Test 2: [1], [1]
        int[] preorder2 = {1};
        int[] inorder2 = {1};
        TreeNode root2 = sol.buildTree(preorder2, inorder2);
        System.out.println("Test 2 - Root: " + root2.val);  // 1
    }
}

JavaScript

construct_binary_tree_from_preorder_and_inorder_traversal_index.js

/**
 * Definition for a binary tree node.
 */
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * Construct a binary tree from preorder and inorder traversal using index tracking.
 * Time: O(n), Space: O(h) where h is height
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
function buildTree(preorder, inorder) {
    if (preorder.length === 0 || inorder.length === 0) {
        return null;
    }

    let preorderIdx = 0;

    const build = (inorderStart, inorderEnd) => {
        if (inorderStart > inorderEnd || preorderIdx >= preorder.length) {
            return null;
        }

        // Root is the current element in preorder
        const rootVal = preorder[preorderIdx];
        preorderIdx++;
        const root = new TreeNode(rootVal);

        // Find root position in inorder
        let rootInorderIdx = -1;
        for (let i = inorderStart; i <= inorderEnd; i++) {
            if (inorder[i] === rootVal) {
                rootInorderIdx = i;
                break;
            }
        }

        // Build left subtree
        root.left = build(inorderStart, rootInorderIdx - 1);

        // Build right subtree
        root.right = build(rootInorderIdx + 1, inorderEnd);

        return root;
    };

    return build(0, inorder.length - 1);
}

// Test cases
if (require.main === module) {
    // Test 1: [3,9,20,15,7], [9,3,15,20,7]
    const preorder1 = [3, 9, 20, 15, 7];
    const inorder1 = [9, 3, 15, 20, 7];
    const root1 = buildTree(preorder1, inorder1);
    console.log(`Test 1 - Root: ${root1.val}`);  // 3

    // Test 2: [1], [1]
    const preorder2 = [1];
    const inorder2 = [1];
    const root2 = buildTree(preorder2, inorder2);
    console.log(`Test 2 - Root: ${root2.val}`);  // 1
}

module.exports = buildTree;

Rust

construct_binary_tree_from_preorder_and_inorder_traversal_index.rs

use std::cell::RefCell;
use std::rc::Rc;

#[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,
        }
    }
}

pub struct Solution;

impl Solution {
    pub fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        if preorder.is_empty() || inorder.is_empty() {
            return None;
        }

        let mut preorder_idx = 0;

        fn build(
            preorder: &[i32],
            inorder: &[i32],
            inorder_start: usize,
            inorder_end: usize,
            preorder_idx: &mut usize,
        ) -> Option<Rc<RefCell<TreeNode>>> {
            if inorder_start > inorder_end || *preorder_idx >= preorder.len() {
                return None;
            }

            // Root is the current element in preorder
            let root_val = preorder[*preorder_idx];
            *preorder_idx += 1;
            let mut root = TreeNode::new(root_val);

            // Find root position in inorder
            let mut root_inorder_idx = inorder_start;
            for (i, &val) in inorder[inorder_start..=inorder_end].iter().enumerate() {
                if val == root_val {
                    root_inorder_idx = inorder_start + i;
                    break;
                }
            }

            // Build left subtree
            root.left = build(
                preorder,
                inorder,
                inorder_start,
                root_inorder_idx.saturating_sub(1),
                preorder_idx,
            );

            // Build right subtree
            root.right = build(
                preorder,
                inorder,
                root_inorder_idx + 1,
                inorder_end,
                preorder_idx,
            );

            Some(Rc::new(RefCell::new(root)))
        }

        build(&preorder, &inorder, 0, inorder.len() - 1, &mut preorder_idx)
    }
}

fn main() {
    // Test 1: [3,9,20,15,7], [9,3,15,20,7]
    let preorder1 = vec![3, 9, 20, 15, 7];
    let inorder1 = vec![9, 3, 15, 20, 7];
    let root1 = Solution::build_tree(preorder1, inorder1);
    if let Some(node) = root1 {
        println!("Test 1 - Root: {}", node.borrow().val);  // 3
    }

    // Test 2: [1], [1]
    let preorder2 = vec![1];
    let inorder2 = vec![1];
    let root2 = Solution::build_tree(preorder2, inorder2);
    if let Some(node) = root2 {
        println!("Test 2 - Root: {}", node.borrow().val);  // 1
    }
}

Go

construct_binary_tree_from_preorder_and_inorder_traversal_index.go

package main

/**
 * Definition for a binary tree node.
 */
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

func buildTree(preorder []int, inorder []int) *TreeNode {
  if len(preorder) == 0 || len(inorder) == 0 {
    return nil
  }

  preorderIdx := 0

  var build func(int, int) *TreeNode
  build = func(inorderStart, inorderEnd int) *TreeNode {
    if inorderStart > inorderEnd || preorderIdx >= len(preorder) {
      return nil
    }

    // Root is the current element in preorder
    rootVal := preorder[preorderIdx]
    preorderIdx++
    root := &TreeNode{Val: rootVal}

    // Find root position in inorder
    rootInorderIdx := -1
    for i := inorderStart; i <= inorderEnd; i++ {
      if inorder[i] == rootVal {
        rootInorderIdx = i
        break
      }
    }

    // Build left subtree
    root.Left = build(inorderStart, rootInorderIdx-1)

    // Build right subtree
    root.Right = build(rootInorderIdx+1, inorderEnd)

    return root
  }

  return build(0, len(inorder)-1)
}

func main() {
  // Test 1: [3,9,20,15,7], [9,3,15,20,7]
  preorder1 := []int{3, 9, 20, 15, 7}
  inorder1 := []int{9, 3, 15, 20, 7}
  root1 := buildTree(preorder1, inorder1)
  println("Test 1 - Root:", root1.Val)  // 3

  // Test 2: [1], [1]
  preorder2 := []int{1}
  inorder2 := []int{1}
  root2 := buildTree(preorder2, inorder2)
  println("Test 2 - Root:", root2.Val)  // 1
}

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

construct_binary_tree_from_preorder_and_inorder_traversal_space_optimized.py

"""
Solution for Construct Binary Tree from Preorder and Inorder Traversal
"""

def solve():
    """Implementation for approach 3 of Construct Binary Tree from Preorder and Inorder Traversal"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

construct_binary_tree_from_preorder_and_inorder_traversal_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Construct Binary Tree from Preorder and Inorder Traversal
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

ConstructBinaryTreeFromPreorderAndInorderTraversalSpaceOptimized.java

/**
 * Solution for Construct Binary Tree from Preorder and Inorder Traversal
 * Approach 3
 */
public class ConstructBinaryTreeFromPreorderAndInorderTraversalSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

construct_binary_tree_from_preorder_and_inorder_traversal_space_optimized.js

/**
 * Solution for Construct Binary Tree from Preorder and Inorder Traversal
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

construct_binary_tree_from_preorder_and_inorder_traversal_space_optimized.rs

/// Solution for Construct Binary Tree from Preorder and Inorder Traversal
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

construct_binary_tree_from_preorder_and_inorder_traversal_space_optimized.go

package main

import "fmt"

// Solution for Construct Binary Tree from Preorder and Inorder Traversal
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Common Mistakes

Watch for these pitfalls

• Off-by-one errors in index calculations: When computing left_size or splitting arrays, be careful with boundary conditions.
• Confusing preorder and inorder: Remember: preorder = root first, inorder = root in the middle.
• Forgetting to advance the preorder pointer: In the index-tracking approach, the pointer must move forward sequentially as you process nodes.
• Not handling empty subarrays: When all nodes go to one side (e.g., a linked-list tree), ensure the recursion bottoms out correctly.
• Assuming duplicate values: The problem guarantees unique values, but always verify input constraints.

Key Insights

1. Preorder structure: preorder[0] is always the root of the current subtree. This is the entry point for every recursive call.

2. Inorder partition: Once you find the root in inorder, the left portion is the left subtree and the right portion is the right subtree. This gives you exact boundaries for recursion.

3. Index mapping: Using a hash map to store inorder indices is the performance key. It transforms an O(n) search into O(1) lookup, keeping overall time at O(n).

4. Size calculation: The number of nodes in the left subtree is root_position_in_inorder - inorder_start. This lets you correctly split preorder without needing to create new arrays.

Interview Tips

Key trade-offs to discuss

• Hash Map vs. Index Tracking: Hash map is O(n) time and space; index tracking is O(n²) worst time but only O(h) extra space. Discuss which matters more in your scenario.
• Why not just search inorder linearly: You can, but it’s slower. Interviews appreciate the optimization of using a hash map.
• Edge cases: Single node (return that node), all nodes on one side (degenerate tree), empty arrays (return null).
• Follow-up — Inorder + Postorder: Same idea, but postorder has root last. The logic adapts naturally.
• Real-world applicability: Serialization formats often store multiple traversals to enable reconstruction. This problem teaches that pattern.

Related Problems

• Maximum Depth of Binary Tree ↗ Easy #104
• Construct Binary Tree from Inorder and Postorder Traversal ↗ Medium #106
• Convert Sorted Array to Binary Search Tree ↗ Easy #108
• Serialize and Deserialize Binary Tree ↗ Hard #297

← Previous
#104 Maximum Depth of Binary Tree Next
#106 Construct Binary Tree from Inorder and Postorder Traversal →