Given pre-order and in-order traversals of a binary tree, write a function to reconstruct the tree.

For example, given the following preorder traversal:

[a, b, d, e, c, f, g]

And the following inorder traversal:

[d, b, e, a, f, c, g]

You should return the following tree:

    a
   / \
  b   c
 / \ / \
d  e f  

To reconstruct a binary tree from its pre-order and in-order traversals, you can use a recursive approach. The idea is to select the root from the pre-order traversal and find its index in the in-order traversal. The elements to the left of this index in the in-order traversal correspond to the left subtree, and the elements to the right correspond to the right subtree.

Here’s a Python function to reconstruct the binary tree:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def build_tree(preorder, inorder):
    if not preorder or not inorder:
        return None

    root_value = preorder[0]
    root = TreeNode(root_value)

    # Find the index of the root value in inorder
    root_index_inorder = inorder.index(root_value)

    # Recursively build left and right subtrees
    root.left = build_tree(preorder[1:1 + root_index_inorder], inorder[:root_index_inorder])
    root.right = build_tree(preorder[1 + root_index_inorder:], inorder[root_index_inorder + 1:])

    return root

# Example usage:
preorder = ['a', 'b', 'd', 'e', 'c', 'f', 'g']
inorder = ['d', 'b', 'e', 'a', 'f', 'c', 'g']

root = build_tree(preorder, inorder)

# Now 'root' contains the reconstructed tree

Javascript

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

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

  const rootValue = preorder[0];
  const root = new TreeNode(rootValue);

  const rootIndexInorder = inorder.indexOf(rootValue);

  root.left = buildTree(
    preorder.slice(1, 1 + rootIndexInorder),
    inorder.slice(0, rootIndexInorder)
  );
  root.right = buildTree(
    preorder.slice(1 + rootIndexInorder),
    inorder.slice(rootIndexInorder + 1)
  );

  return root;
}

// Example usage:
const preorder = ['a', 'b', 'd', 'e', 'c', 'f', 'g'];
const inorder = ['d', 'b', 'e', 'a', 'f', 'c', 'g'];

const root = buildTree(preorder, inorder);
console.log(root);

Java

class TreeNode {
    char value;
    TreeNode left, right;

    public TreeNode(char item) {
        value = item;
        left = right = null;
    }
}

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

        char rootValue = preorder[0];
        TreeNode root = new TreeNode(rootValue);

        int rootIndexInorder = 0;
        while (inorder[rootIndexInorder] != rootValue) {
            rootIndexInorder++;
        }

        root.left = buildTree(
            Arrays.copyOfRange(preorder, 1, 1 + rootIndexInorder),
            Arrays.copyOfRange(inorder, 0, rootIndexInorder)
        );
        root.right = buildTree(
            Arrays.copyOfRange(preorder, 1 + rootIndexInorder, preorder.length),
            Arrays.copyOfRange(inorder, rootIndexInorder + 1, inorder.length)
        );

        return root;
    }

    public static void main(String[] args) {
        char[] preorder = {'a', 'b', 'd', 'e', 'c', 'f', 'g'};
        char[] inorder = {'d', 'b', 'e', 'a', 'f', 'c', 'g'};

        BinaryTreeBuilder builder = new BinaryTreeBuilder();
        TreeNode root = builder.buildTree(preorder, inorder);

        // Now 'root' contains the reconstructed tree
    }
}