Solving Construct Binary Tree from Preorder and Inorder in JavaScript: Step-by-Step Guide

Reconstructing a binary tree from its traversal outputs is one of the most classic problems in computer science. Among the many variations, building a tree from its preorder and inorder traversal arrays is especially popular in coding interviews because it tests your understanding of recursion, tree structure, and array manipulation all at once. In this tutorial, we will break down the problem, understand the underlying theory, and implement a clean, efficient solution in JavaScript.

What Is the Problem?

Given two arrays — preorder and inorder — that represent the preorder and inorder traversals of a binary tree, your task is to reconstruct and return the root of the original tree. You may assume that the values in the tree are unique, which is a critical constraint that makes the problem solvable.

Let's quickly recall the two traversal types:

Preorder visits nodes in the order: root, left subtree, right subtree.
Inorder visits nodes in the order: left subtree, root, right subtree.

For example, given the following inputs:

preorder = [3, 9, 20, 15, 7]
inorder  = [9, 3, 15, 20, 7]

The reconstructed tree should look like this:

Why This Problem Matters

This problem is more than just an interview exercise. It teaches several foundational concepts that appear across real-world engineering tasks:

Recursion and divide-and-conquer: You learn how to break a large problem into smaller, structurally identical subproblems.
Tree fundamentals: Understanding traversal orders is essential for working with file systems, DOM trees, ASTs, and database indexes.
Index mapping: Optimizing the solution requires recognizing when repeated linear scans can be replaced with hash-based lookups.
State management: Tracking pointers across recursive calls mirrors how you manage state in complex applications.

Mastering this problem builds the mental model you need for more advanced topics like serializing and deserializing trees, building expression trees, and parsing nested structures.

The Core Insight

The key observation is that the first element of the preorder array is always the root of the current subtree. Once you know the root, you can locate that same value in the inorder array. Everything to the left of that position in the inorder array belongs to the left subtree, and everything to the right belongs to the right subtree.

Let's walk through the example step by step:

preorder[0] = 3 is the root.
In inorder, 3 is at index 1. So the left subtree has 1 element ([9]) and the right subtree has 3 elements ([15, 20, 7]).
Recursively apply the same logic to the left and right portions of both arrays.

Because preorder always lists the root first, you can use a global pointer that advances through the preorder array as you build each node. The inorder array tells you how many nodes belong to each side, which lets you slice the recursion correctly.

Step-by-Step Implementation

Let's start with a straightforward recursive solution that uses array slicing. This version is easy to understand, even if it is not the most efficient.

// Definition for a binary tree node.
function TreeNode(val, left, right) {
  this.val = (val === undefined ? 0 : val);
  this.left = (left === undefined ? null : left);
  this.right = (right === undefined ? null : right);
}

function buildTree(preorder, inorder) {
  if (preorder.length === 0 || inorder.length === 0) {
    return null;
  }

  // The first element of preorder is always the root.
  const rootVal = preorder[0];
  const root = new TreeNode(rootVal);

  // Find the index of rootVal in inorder.
  const rootIndex = inorder.indexOf(rootVal);

  // Elements to the left of rootIndex form the left subtree.
  const leftInorder = inorder.slice(0, rootIndex);
  // Elements to the right form the right subtree.
  const rightInorder = inorder.slice(rootIndex + 1);

  // The corresponding preorder slices have the same sizes.
  const leftPreorder = preorder.slice(1, 1 + leftInorder.length);
  const rightPreorder = preorder.slice(1 + leftInorder.length);

  root.left = buildTree(leftPreorder, leftInorder);
  root.right = buildTree(rightPreorder, rightInorder);

  return root;
}

This solution works and is very readable. However, it has a few inefficiencies. The indexOf call runs in linear time, and the slice operations create new arrays on every recursive call. For large inputs, this can become expensive.

Optimizing with a Hash Map and Index Pointers

We can improve performance by avoiding array slicing entirely. Instead, we pass index boundaries into the inorder array and use a hash map to look up the root's position in constant time. We also maintain a mutable pointer into the preorder array that advances as we create each node.

function buildTreeOptimized(preorder, inorder) {
  // Map each value to its index in the inorder array for O(1) lookup.
  const inorderIndexMap = new Map();
  for (let i = 0; i < inorder.length; i++) {
    inorderIndexMap.set(inorder[i], i);
  }

  // Use a wrapper object so the pointer can be mutated across recursive calls.
  let preorderPointer = 0;

  function helper(leftBound, rightBound) {
    // If there are no elements to construct, return null.
    if (leftBound > rightBound) {
      return null;
    }

    // Pick the next element from preorder as the root.
    const rootVal = preorder[preorderPointer];
    preorderPointer++;

    const root = new TreeNode(rootVal);

    // Split inorder around the root's index.
    const rootIndex = inorderIndexMap.get(rootVal);

    // Build left subtree first, because preorder visits left before right.
    root.left = helper(leftBound, rootIndex - 1);
    root.right = helper(rootIndex + 1, rightBound);

    return root;
  }

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

Notice the order of the recursive calls. Because preorder visits the root, then the entire left subtree, then the entire right subtree, we must build the left child before the right child. This ensures the preorderPointer advances in the correct sequence.

Testing the Solution

To verify that the reconstruction is correct, we can write a helper function that performs an inorder traversal and compare the output to the original input.

function inorderTraversal(root) {
  const result = [];
  function traverse(node) {
    if (node === null) return;
    traverse(node.left);
    result.push(node.val);
    traverse(node.right);
  }
  traverse(root);
  return result;
}

function preorderTraversal(root) {
  const result = [];
  function traverse(node) {
    if (node === null) return;
    result.push(node.val);
    traverse(node.left);
    traverse(node.right);
  }
  traverse(root);
  return result;
}

const preorder = [3, 9, 20, 15, 7];
const inorder = [9, 3, 15, 20, 7];

const tree = buildTreeOptimized(preorder, inorder);

console.log(preorderTraversal(tree)); // [3, 9, 20, 15, 7]
console.log(inorderTraversal(tree));  // [9, 3, 15, 20, 7]

If both traversals match the original inputs, the reconstruction is correct. This is a great sanity check to include in your test suite.

Handling Edge Cases

A robust solution should account for several edge cases:

Empty arrays: When both preorder and inorder are empty, return null.
Single node: A tree with one element should return a single node with no children.
Left-skewed tree: A tree where every node has only a left child, such as preorder = [1, 2, 3] and inorder = [3, 2, 1].
Right-skewed tree: A tree where every node has only a right child, such as preorder = [1, 2, 3] and inorder = [1, 2, 3].
Invalid input: If the two arrays do not represent the same tree (for example, they contain different values), the algorithm may produce incorrect results or throw errors. In production code, you should validate the inputs first.

Here is a small validation helper you can add:

function validateInput(preorder, inorder) {
  if (preorder.length !== inorder.length) {
    throw new Error("Preorder and inorder must have the same length.");
  }
  const set = new Set(inorder);
  for (const val of preorder) {
    if (!set.has(val)) {
      throw new Error("Preorder and inorder must contain the same values.");
    }
  }
}

Best Practices

As you implement and refine this solution, keep the following best practices in mind:

Prefer the optimized approach in interviews: The hash map and pointer-based solution runs in O(n) time and O(n) space, which is the expected complexity for this problem.
Use immutable patterns when clarity matters: The slicing version is easier to explain and reason about, making it a good starting point before optimizing.
Document your assumptions: Clearly state that all values are unique. Without this assumption, the problem becomes ambiguous and may require additional constraints.
Write traversal tests: Always verify your reconstructed tree by re-traversing it and comparing against the original arrays.
Avoid global mutable state in production code: In the optimized version, the preorderPointer is shared across recursive calls. Wrapping it in a closure keeps it contained, but be cautious when extending the function.
Consider iterative alternatives: For extremely deep trees, recursion may cause stack overflow. An iterative version using an explicit stack is possible but significantly more complex, so only pursue it when necessary.

Complexity Analysis

Let's summarize the time and space complexity of both approaches:

Slicing version: O(n²) time in the worst case due to repeated indexOf and slice calls, and O(n²) space from creating new arrays at each level.
Optimized version: O(n) time because each node is processed once and the hash map provides O(1) lookups. Space is O(n) for the hash map plus O(h) for the recursion stack, where h is the height of the tree.

In a balanced tree, h is O(log n), so the total space is O(n). In a skewed tree, h is O(n), which still results in O(n) total space because the hash map dominates.

Conclusion

Constructing a binary tree from its preorder and inorder traversals is a powerful exercise that strengthens your understanding of recursion, tree structure, and algorithmic optimization. By starting with a clear slicing-based solution and then refining it with a hash map and index pointers, you build both intuition and performance awareness. The key takeaway is that preorder tells you the root and inorder tells you the boundaries of each subtree — once you internalize that relationship, the recursive structure falls into place naturally. With the patterns and best practices covered here, you are well equipped to tackle this problem confidently in interviews and apply the same divide-and-conquer thinking to more complex tree-related challenges.