106. Construct Binary Tree from Inorder and Postorder Traversal

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.

Approach 1: recursion dfs


class Solution {
    int postIndex;
    int[] postOrder;
    int[] inOrder;
    HashMap mapOfIndex = new HashMap();

    public TreeNode dfs(int leftIndex, int rightIndex) {
        // if there is no elements to construct subtrees
        if (leftIndex > rightIndex)
            return null;

        // pick up postIndex element as a root
        int rootVal = postOrder[postIndex];
        TreeNode root = new TreeNode(rootVal);

        // root splits inorder list into left and right subtrees
        int index = mapOfIndex.get(rootVal);

        // recursion
        postIndex--;
        // build right subtree recursively
        root.right = dfs(index + 1, rightIndex);
        // build left subtree recursively
        root.left = dfs(leftIndex, index - 1);
        return root;
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postOrder = postorder;
        this.inOrder = inorder;
        // start from the last postorder element
        postIndex = postOrder.length - 1;

        // build a hashmap value -> its index
        int index = 0;
        for (Integer val : inOrder)
            mapOfIndex.put(val, index++);
        return dfs(0, inOrder.length - 1);
    }
}

Time Complexity: O(n) and Space Complexity: O(n)

The problem "Construct Binary Tree from Inorder and Postorder Traversal" involves reconstructing a binary tree given two of its traversal sequences: inorder and postorder. The challenge is to utilize the properties of these two traversal orders to accurately build the tree.

Inorder traversal visits nodes in the left subtree, the root node, and the right subtree. Postorder traversal visits nodes in the left subtree, the right subtree, and finally the root node. Using both of these traversals together provides sufficient information to reconstruct the original binary tree.

Problem Statement

Given two integer arrays `inorder` and `postorder` where:

`inorder` is the inorder traversal of the binary tree.
`postorder` is the postorder traversal of the binary tree.

Construct and return the binary tree. It is guaranteed that there is only one valid answer.

Approach

To solve this problem, we need to leverage the following properties of the inorder and postorder traversals:

In the postorder traversal, the last element is the root of the tree.
In the inorder traversal, the root divides the array into two parts: the left subtree (elements before the root) and the right subtree (elements after the root).

By using the postorder array to identify the root and the inorder array to determine the left and right subtrees, we can recursively construct the tree.

We can perform the following steps:

Find the root node using the last element in the postorder array.
Find the index of this root node in the inorder array, which separates the left and right subtrees.
Recursively repeat this process for the left and right subtrees using the appropriate parts of the inorder and postorder arrays.
Return the constructed tree once all recursive calls are complete.

Algorithm

The algorithm can be described as follows:

Start with the full inorder and postorder arrays.
The last element of the postorder array is the root of the tree.
Find the index of the root in the inorder array, which divides the array into two parts: the left and right subtrees.
Recursively construct the left and right subtrees using the left and right parts of the inorder and postorder arrays.
Repeat the process until the entire tree is constructed.

Example

Consider the following inorder and postorder traversals:

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

To construct the binary tree: - The last element in the postorder array is 3, which is the root of the tree. - Find 3 in the inorder array. It splits the inorder array into two parts: - Left subtree: [9] - Right subtree: [15, 20, 7] - Recursively construct the left and right subtrees.

The binary tree is successfully reconstructed with 3 as the root, 9 as the left child, and 20 as the right child, with 15 and 7 as children of 20.

Code Implementation

Below is the Python implementation of the algorithm to construct the binary tree from inorder and postorder traversals:

In this code: - We first check if the inorder or postorder arrays are empty. If they are, we return None (no tree). - We pop the last element from the postorder array to get the root value. - We find the index of this root value in the inorder array to determine the left and right subtrees. - We recursively call the function to build the left and right subtrees using the appropriate subarrays. - Finally, we return the root of the tree.

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the tree. This is because we process each node exactly once during the recursive calls.

The space complexity is O(n), where n is the number of nodes in the tree. This accounts for the space used by the call stack during recursion, as well as the space used to store the inorder and postorder arrays.

Conclusion

The "Construct Binary Tree from Inorder and Postorder Traversal" problem requires a deep understanding of tree traversal and recursion. By using the properties of inorder and postorder traversals, we can successfully reconstruct the original binary tree. This problem is an excellent way to practice recursion and working with tree structures.