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

By | January 31, 2024

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
}
}