Construct Binary Tree from Inorder and Postorder Traversal: A Step-by-Step Guide

When it comes to binary trees, traversals play a key role in understanding the structure and function of the tree. If you’re preparing for coding interviews or working on binary tree problems, the “Construct Binary Tree from Inorder and Postorder Traversal” is an essential problem that tests both your understanding of recursion and tree traversal techniques.

In this blog post, we’ll break down this problem step-by-step and provide a clear, actionable approach to solving it. Let’s dive right in!

Understanding Tree Traversals

Before we start constructing a binary tree from its traversals, let's quickly review the two types of traversals we are working with:

Inorder Traversal: In this traversal method, the nodes are visited in the following order: Left subtree → Root → Right subtree.
Postorder Traversal: In postorder traversal, nodes are visited in this order: Left subtree → Right subtree → Root.

Key Insight: The last element of the postorder traversal is always the root of the tree or the current subtree. This fact forms the backbone of our solution.

Problem Explanation

Given two arrays:

Inorder traversal array.
Postorder traversal array.

You need to construct the binary tree that corresponds to these traversal arrays.

For example:

Inorder: [9, 3, 15, 20, 7]
Postorder: [9, 15, 7, 20, 3]

We’ll use these two traversals to reconstruct the original binary tree.

Step-by-Step Solution

Here’s the strategy we’ll follow:

Identify the root: The last element of the postorder array is always the root of the tree. In this case, the root is 3.
Split the inorder array: Find the index of the root in the inorder array. Elements to the left of the root form the left subtree, and elements to the right form the right subtree.
Recursively build the tree: Recursively apply the same process to construct both the left and right subtrees using the remaining elements in the postorder and inorder arrays.

Code Implementation

Here's a Python solution that follows this approach:

class Solution {
	    public TreeNode buildTree(int[] inorder, int[] postorder) {
	        // Use a helper method to build the tree recursively.
	        return buildTree(inorder, 0, inorder.length - 1, postorder, 
0, postorder.length - 1);
	    }

	    private TreeNode buildTree(int[] inorder, int inStart, int inEnd, 
int[] postorder, int postStart, int postEnd) {
	        if (inStart > inEnd || postStart > postEnd) return null;

	        // The last element in postorder is the root.
	        TreeNode root = new TreeNode(postorder[postEnd]);

// Find the root in inorder array to divide the left and 
right subtrees.
	        int inRoot = inStart;
	        while (inorder[inRoot] != root.val) inRoot++;

	        // Calculate the size of the left subtree.
	        int leftSize = inRoot - inStart;

	        // Recursively build the left and right subtrees.
	        root.left = buildTree(inorder, inStart, inRoot - 1, postorder, 
postStart, postStart + leftSize - 1);
	        root.right = buildTree(inorder, inRoot + 1, inEnd, postorder, 
postStart + leftSize, postEnd - 1);

	        return root;
	    }
	}

Visualization and Walkthrough

Let’s walk through the example with Inorder and Postorder arrays:

Inorder: [9, 3, 15, 20, 7]
Postorder: [9, 15, 7, 20, 3]

Step 1: Identify the Root

The last element in the postorder array is 3, so 3 is the root of the tree.

Tree:

Step 2: Split the Inorder Array

The root 3 is located at index 1 in the inorder array. Elements to the left of 3 ([9]) form the left subtree, and elements to the right of 3 ([15, 20, 7]) form the right subtree.

Inorder: [9] [3] [15, 20, 7]

Postorder: [9] [15, 7, 20]

Step 3: Recursively Build the Right Subtree

Next, we pick the last element from the postorder array (20) as the root of the right subtree.

Tree:

Now, split the right side of the inorder array [15, 20, 7] around 20. The left part ([15]) forms the left subtree of 20, and the right part ([7]) forms the right subtree.

Step 4: Build Left and Right Subtrees for Node 20

Postorder: 15 (left subtree), 7 (right subtree).

Finally, we can complete the construction of the tree.

Final Tree:

/ \

9 20

/ \

15 7

Conclusion

The problem of constructing a binary tree from inorder and postorder traversals is a great exercise in recursion and understanding how tree traversal techniques interrelate. By recognizing the root nodes in the postorder traversal and using the inorder traversal to split the tree, we can efficiently reconstruct the binary tree.

If you’re preparing for technical interviews or just honing your algorithmic skills, mastering this problem will strengthen your understanding of binary trees and recursion.

Key Takeaways:

The last element of the postorder array is the root of the current subtree.
The inorder array helps to determine how to split the tree into left and right subtrees.
Use recursion to solve both the left and right subtrees until the entire tree is built.

FAQs

Q: Can I solve this problem iteratively? A: Although recursion is the most intuitive approach to solve this problem, it is possible to implement an iterative solution using stacks, though it’s more complex.

Q: What is the time complexity of this solution? A: The time complexity of this solution is O(n), where n is the number of nodes in the tree. This is because each node is processed once during the construction of the tree.

By mastering this problem, you’re one step closer to mastering binary trees! Keep practicing, and feel free to ask questions or leave comments below. Happy coding!