Construct Binary Tree from Postorder and Inorder Traversal

Problem:

Given Postorder and inorder traversal array of a binary tree, construct the binary tree.

Note the binary tree is not binary search tree, means the nodes in left branch don't have to be smaller than the root and the nodes in right branch don't have to be bigger than root. We can assume there is no duplicate node values.

For example, given

postorder = [9,15,7,20,3]

inorder = [9,3,15,20,7]

We should construct the following binary tree:

    3

   / \

  9  20

    /  \

   15   7

Solution:

For postorder array, the root node 3 is at the last index, the left and right branch nodes are in subarray [9,15,7,20]. However, since this is not binary search tree, with postorder array alone, we won't be able to find out which nodes are in the left branch and which nodes are in the right branch. 

We have to use another traversal array to find out. Since we have inorder array, and we have the root node 3, we can tell, the root node divide the inorder array into 2 halves. The left half is the left branch and the right half is the right branch. 

From the inorder array, we find how many nodes are in the left branch and how many nodes are in the right branch. Then we can go back the postorder array, divide the subarray into 2 halves. In our case 1 is on the left branch and 3 are on the right branch, so we have [9] and [15,7,20]. The subarray [15,7,20] obeys the same rule,20 is the root node, and the rest of nodes are in left and right branches. Following the above process, we can find the proper division from inorder array.

To find the root node index from inorder array, we can use binary search with cost O(logN), however, we can build a value to index HashMap in order to get the index with cost O(1).

In the recursive code, we process the postorder array from right to left. When the inorder array reaches the single node level, the postorder array is pointing at the same node the inorder array element point at.

import java.util.*;
class Solution {
  private Map<Integer, Integer> valueToIndex;
  private int indexP;
  private int[] inOrder;
  private int[] postOrder;
  public static void main(String...args) {
    Solution sol = new Solution();
    Node root = sol.buildTree(new int[]{9,3,15,20,7}, new int[]{9,15,7,20,3});
    printInOrder(root);
    System.out.println();
    printPostOrder(root);
    System.out.println();
 
  }

  private static void printInOrder(Node root) {
    if(root == null) return;
    printInOrder(root.left);
    System.out.print(root.value + " ");
    printInOrder(root.right);
  }

  private static void printPostOrder(Node root) {
    if(root == null) return;
    printPostOrder(root.left);
    printPostOrder(root.right);
    System.out.print(root.value + " ");
  }

  public Node buildTree(int[] inOrder, int[] postOrder) {
    this.postOrder = postOrder;
    this.inOrder = inOrder;
    valueToIndex = new HashMap<>();
    for(int i = 0; i < inOrder.length; i++) {
      valueToIndex.put(inOrder[i], i);
    }
    indexP = postOrder.length - 1;
    return build(0, postOrder.length-1);
  }

  private Node build(int start, int end) {
    if(start > end) return null;
    int val = postOrder[indexP];
    int index = valueToIndex.get(val);
    indexP--;
    Node root = new Node(val, null, null);
    root.right = build(index+1, end);
    root.left = build(start, index-1);
    return root;
  }

  private static class Node {
    int value;
    Node left;
    Node right;
    public Node(int value, Node left, Node right) {
      this.value = value;
      this.left = left;
      this.right = right;
    }
  }
}

The time complexity is O(N) for visiting each node in postorder array, the space complexity is also O(N) for the HashMap.

see also: Construct Binary Tree from Preorder and Inorder Traversal