Reconstruct binary tree from in-order and pre-order

Back to index

The problem statement:

Given two integer arrays representing the in-order and pre-order traversals of a binary tree, reconstruct the binary tree.

This problem seems easier using recursion. The idea is that the pre-order can tell us what the root is and the in-order what its left and right children are. A first attempt might iterate through the in-order traversal and find the root from the pre-order traversal. However we can use a shortcut. The pre-order traversal places the root first, then the left sub-tree and then the right sub-tree. Therefore if we construct the left sub-tree first we don't need to use a loop to find the root. It will simply be the earliest element of the pre-order traversal that we have not used.

class Solution {
  Map<Integer, Integer> inorderIndex = new HashMap<>();
  int preorderPointer;
  int[] preorder;

  public TreeNode buildTree(int[] preorder, int[] inorder) {
    for (int i = 0; i < inorder.length; i++) {
      this.inorderIndex.put(inorder[i], i);
    }

    this.preorderPointer = 0;
    this.preorder = preorder;

    return this.buildTreeInner(0, preorder.length - 1);
  }

  public TreeNode buildTreeInner(int leftPointer, int rightPointer) {
    if (leftPointer > rightPointer) {
      return null;
    }

    int rootVal = this.preorder[this.preorderPointer];
    TreeNode root = new TreeNode(rootVal);
    int rootIndex = this.inorderIndex.get(rootVal);

    this.preorderPointer++;
    root.left = this.buildTreeInner(leftPointer, rootIndex - 1);
    root.right = this.buildTreeInner(rootIndex + 1, rightPointer);

    return root;
  }
}