Construct Binary Tree from Inorder and Postorder Traversal

Solving leetcode 106

The Problem

Given two integer arrays, inorder and postorder, where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Quick Recap

In case you have forgotten, inorder traversal visits nodes by visiting the left, parent and then the right:

In contrast, postorder traversal visits the left and right children and then the parent.

The above diagrams show the completed trees; we only receive the visited lists as inputs:

Getting Started

Let's start by exploring the problem domain with a simple input list:

If the list represents a postorder collection, it will visit the children first and then the parent. So from the simple example, we can tell that the tree is a parent node with one child. However, we cannot know whether the tree has a right or a left child. So assuming the list is in postorder, then the following trees are possible:

Similarly, If the list is inorder, the tree's shape is one parent with a single child. However, unlike in postorder, we have no way of knowing which one is the parent, as can be seen by looking at the possible combinations:

To conclude, with postorder:

• We can Find the parent and child.
• We cannot discern what side the child is on.

And with inorder:

• We can find the side if we know the parent.
• We cannot know to tell the parent and child apart.

Now let's combine these findings. The postorder findings give the parent, applied to inorder gives us the side of the child node.

So using this simple example, we have proven that it is possible to calculate the tree's shape if we have both inorder and postorder lists. In the next section, I will collate these findings to show the solution to the problem.

Solution

In the last section, we showed where to find the parent node in a postorder list, which is always the last node visited.

In list form, this looks like this:

If we know the length of the left and right groups, postorder always visit them in the order of all the left nodes, then all the right nodes and finally the highest parent node. In the left and right groups, the last node is always the highest and so will be the direct child of the parent you are comparing to.

You can use inorder to find the size of the left and right groups. This is because inorder traversal always visits the highest node between the left and right sides, as we can see in this tree.

In list form, this looks like this:

As we can see, we have two groups, which we can now use in the postorder list to find the parent's direct left and right child, as once you know how big the left and the right group is, the immediate child is always the last node of that group.

The above algorithm outlines the steps needed to calculate any tree node's children. To find the right children on the right side of the root node, you take the right groups of both inorder and postorder:

Now the highest node is C (the most right node of post order)

To find the children, we use inorder to split:

And reapply to postorder:

This allows us to draw in the children into the tree:

As the left and right groups for the next level are of size one, they must be leaf nodes, so the tree's right side must be complete.

The exact process applies to find the top node's left side. Start by taking the left groups:

Use postorder to identify the current node:

Use inorder to split:

At this point we can reapply to postorder:

That last step isn't strictly needed, as we know that there is only one node. However, the rules we have outlined work for any length so its better to be consistent.

Now we are ready to complete the tree:

Appendix

To show how this works in code, I have added my Java solution below: