Binary Tree Rebuilding from Preorder and Inorder Traversals

A traversal flattens a binary tree into a list of values in a fixed visiting order. A preorder traversal visits the root first, then the left subtree, then the right subtree; an inorder traversal visits the left subtree, then the root, then the right subtree. Given both traversals of the same tree — whose node values are all distinct — your job is to rebuild the original tree and return its root node.

Signature

type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null };

// preorder and inorder are arrays of the same distinct values, describing one tree.
// Returns the root TreeNode, or null when the tree is empty.
function binaryTreeRebuildingFromTraversals(
  preorder: number[],
  inorder: number[],
): TreeNode | null;

Examples

// preorder visits root-first; inorder splits left | root | right.
binaryTreeRebuildingFromTraversals([3, 9, 20, 15, 7], [9, 3, 15, 20, 7]);
// →        3
//         / \
//        9   20
//            / \
//          15   7
// returns { val: 3, left: { val: 9, left: null, right: null },
//           right: { val: 20, left: { val: 15, ... }, right: { val: 7, ... } } }

// A single node — both arrays hold exactly that value.
binaryTreeRebuildingFromTraversals([42], [42]);
// returns { val: 42, left: null, right: null }

Notes

• Distinct values — every value in the tree is unique, so a value found in preorder appears exactly once in inorder. Duplicates would make the split point ambiguous and break the approach.
• Same tree — both arrays describe the same tree, so they have equal length and the same set of values.
• Empty input — when both arrays are empty, return null. There is no tree to build.
• Return shape — return actual node objects of the form { val, left, right }, with left/right set to null where a child is absent. Don't return the arrays or a serialized string.