Solving Construct Binary Tree from Preorder and Inorder Traversal

The "Construct Binary Tree from Preorder and Inorder Traversal" problem involves rebuilding a binary tree from its preorder and inorder traversal sequences.

Problem Statement

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.

Example

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

The constructed binary tree is:

Solution Approach - Recursive Construction

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  let preIndex = 0;
  const inMap = new Map<number, number>();
  inorder.forEach((val, index) => inMap.set(val, index));

  function arrayToTree(left: number, right: number): TreeNode | null {
    if (left > right) return null;

    const rootVal = preorder[preIndex++];
    const rootValueIndex = inMap.get(rootVal);

    if (rootValueIndex === undefined) {
      throw new Error(`Key ${rootVal} not found in map.`);
    }

    const root = new TreeNode(rootVal);

    root.left = arrayToTree(left, rootValueIndex - 1);
    root.right = arrayToTree(rootValueIndex + 1, right);

    return root;
  }

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

Breaking Down the Solution

• Map for Inorder Indices: Create a map to quickly find the index of each value in the inorder sequence.
• Recursive Construction: Recursively build the left and right subtrees using the indices in the map to find the dividing point.
• Preorder Traversal: The preorder array guides the creation of each node, starting from the root.

Conclusion

Constructing a binary tree from preorder and inorder traversals is an intriguing challenge that tests understanding of tree properties and traversal techniques.