Construct Binary Tree from Postorder and Inorder Traversal

In this article, we’ll see how we are able to construct a binary tree using two basic binary tree traversals - postorder and inorder.

Structure of BinaryTreeNode

1
2
3
4
5
6
struct BinaryTreeNode {
  int key;
  BinaryTreeNode * left;
  BinaryTreeNode * right;
  BinaryTreeNode(int x): val(x), left(NULL), right(NULL) {}
};

Postorder: where we first visit the root node of the tree, then the left and eventually the right subtree.

Pseudo Code:

1
2
3
4
5
6
7
8
void preorderTraversal(BinaryTreeNode * root) {
  if (root == nullptr)
    return;

  cout << root - > key << " ";
  preorderTraversal(root - > left);
  preorderTraversal(root - > right);
}

Inorder: We first traverse the left subtree, then visit the root node, and then the right subtree.

Pesudo Code:

1
2
3
4
5
6
7
8
void inorderTraversal(BinaryTreeNode * root) {
  if (root == NULL)
    return;

  inorderTraversal(root - > left);
  cout << root - > key << ' ';
  inorderTraversal(root - > right);
}

Example Input:
Postorder = [ 10, 18, 9, 22, 4]
Inorder = [10, 4, 18, 22, 9]

Output:

Now to construct our binary tree, we first choose the root node which is the last node within the postorder traversal. So, find that node within the inorder traversal and state the boundary of its left and right subtree, meaning all the nodes to the left of the node in inorder would be within the left subtree and same goes for the right hand side of the node. Repeating the above steps we generate our tree.

To illustrate further, consider the above inorder and postorder traversals.
Here our root node is 4, now when we find 4 in the inorder traversal and separate the left and right subtree, left: [ 10 ] and right : [ 18, 22, 9 ]. And now our problem is reduced to:

Left recursion:
Inorder: [ 10 ]
Postorder: [ 10 ]

Right recursion:
Inorder: [ 18 22 9 ]
Postorder: [ 18 9 22 ]

Algorithm:

1. Make a variable postIdx initialized to length -1 to pick the next required node in the next recursive call from the preorder.

2. Initialize a new tree node with the value picked in the first step.

3. Traverse and find the node in the inorder traversal.

4. Now make two recursive calls, one for the left subtree passing value before the inorder index and one for the right subtree with value after the inorder index.

5. Return the initialized node.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
    unordered_map < int, int > nodeIndices;
    int postOrderIndex = 0;

    BinaryTreeNode * buildTree(vector < int > & inorder, vector < int > & postorder) {
      for (int o = 0; o < postorder.size(); o++)
        nodeIndices.insert({
          inorder.at(o),
          o
        });

      postOrderIndex = postorder.size() - 1;
      return buildBinaryTree(inorder, postorder, 0, inorder.size() - 1);
    }

    BinaryTreeNode * buildBinaryTree(vector < int > & inorder, vector < int > & postorder, int start, int end) {
      if (start > end) return nullptr;

      BinaryTreeNode * root = new BinaryTreeNode(postorder.at(postOrderIndex--));

      int index = nodeIndices.at(root - > val);
      root - > right = buildBinaryTree(inorder, postorder, index + 1, end);
      root - > left = buildBinaryTree(inorder, postorder, start, index - 1);

      return root;
    }

Note: We could have used linear search to search out the node with values within the inorder but we optimized the map variant unordered_map which reduced the search complexity to about O(1).

Time complexity: As we traverse only the postorder array and search through inorder in constant time, our complexity is O(n).
Space complexity: O(n), the extra space is used for storing indexes and making recursion calls.