Construct Binary Tree from Preorder and Postorder Traversal

Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree. If there exist multiple answers, you can return any of them.

Approach 1: recursive


class Solution {
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        return rec(pre, 0, pre.length - 1, post, 0, post.length - 1);
    }

    public TreeNode rec(int[] pre, int i, int j, int[] post, int m, int n) {
        if (i == j) {
            return new TreeNode(pre[i]);
        }
        TreeNode node = new TreeNode(pre[i]);
        if (i < j) {
            int leftNode = pre[i + 1];
            int end = 0;
            for (int p = m; p < n; p++) {
                if (post[p] == leftNode) {
                    end = p;
                    break;
                }
            }
            int size = end - m + 1;
            if (i + 1 <= i + size) {
                node.left = rec(pre, i + 1, i + size, post, m, end);
            }
            if (i + size <= j && end + 1 <= n - 1) {
                node.right = rec(pre, i + size + 1, j, post, end + 1, n - 1);
            }

        }
        return node;
    }
}

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

The "Construct Binary Tree from Preorder and Postorder Traversal" problem involves reconstructing a binary tree using the preorder and postorder traversal arrays. Unlike other tree traversal problems, this one is more complex because both the preorder and postorder arrays are required. However, the key insight is that both traversals give us the position of nodes in the tree, and we can use this information to reconstruct the tree.

Preorder traversal visits the nodes in the order: root, left subtree, right subtree. Postorder traversal visits nodes in the order: left subtree, right subtree, root. These two properties, along with the fact that we know the binary tree is unique, allow us to efficiently reconstruct the original tree.

Problem Statement

Given two integer arrays `preorder` and `postorder`, which represent the preorder and postorder traversals of a binary tree, construct and return the binary tree. It is guaranteed that there is only one valid answer.

The tree node structure is given above. We need to construct the binary tree from the provided traversals.

Approach

To solve this problem, we need to utilize the following key properties of the preorder and postorder traversals:

In preorder, the first element is always the root of the tree or subtree.
In postorder, the last element is always the root of the tree or subtree.
The left and right subtrees are recursively constructed by splitting the preorder and postorder arrays accordingly.

The challenge is to correctly identify and separate the left and right subtrees during the reconstruction. The idea is to use the preorder array to select the root node and the postorder array to separate the subtrees, continuing recursively until the entire tree is built.

The recursive procedure can be outlined as follows:

Start with the first element of the preorder array to identify the root of the tree or subtree.
Find the corresponding node in the postorder array to divide the tree into left and right subtrees.
Recursively build the left and right subtrees by repeating the above steps for the remaining nodes in the preorder and postorder arrays.
Continue until all nodes are processed and the binary tree is constructed.

Algorithm

The algorithm can be broken down into the following steps:

Start by taking the root from the first element of the preorder array.
Find this root node's position in the postorder array to separate the left and right subtrees.
Recursively process the left subtree using the remaining nodes in the preorder and postorder arrays.
Recursively process the right subtree in the same way.
Repeat the process until the entire tree is built.

Example

Consider the following preorder and postorder traversals:

        Preorder: [1, 2, 4, 5, 3]
        Postorder: [4, 5, 2, 3, 1]

To construct the binary tree: - The first element in the preorder array is 1, which is the root of the tree. - Find 1 in the postorder array, and separate the left and right subtrees based on this position. - Recursively build the left and right subtrees from the remaining nodes in the preorder and postorder arrays.

In this case: - 1 is the root. - 2 is the left child of 1, and 3 is the right child of 1. - 4 and 5 are the left and right children of 2, respectively.

Code Implementation

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

In this code: - The root is selected from the first element of the preorder array. - The left child is identified using the next element in the preorder array and the corresponding position in the postorder array. - The preorder and postorder arrays are split into left and right subarrays, and the function is recursively called to build the left and right subtrees. - The process continues until all nodes are processed and the tree is fully reconstructed.

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 while recursively constructing the tree.

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 and the storage of the preorder and postorder arrays.

Conclusion

The "Construct Binary Tree from Preorder and Postorder Traversal" problem is a challenging tree reconstruction problem that requires careful handling of traversal properties. By leveraging the fact that the root node appears in specific positions in both traversals, we can recursively construct the binary tree. This problem is a good exercise for understanding recursive tree-building and working with multiple traversal orders.