# Construct Binary Tree from Preorder and Postorder Traversal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal)
Canonical: https://scaleengineer.com/dsa/problems/construct-binary-tree-from-preorder-and-postorder-traversal
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer)
**Data structures:** Array, Hash Table, Tree, Binary Tree
---
## Problem
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.

**Example 1:**

![](https://assets.glich.co/dsa/construct-binary-tree-from-preorder-and-postorder-traversal/image0.jpg) 

**Input:** preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
**Output:** [1,2,3,4,5,6,7]

**Example 2:**

**Input:** preorder = [1], postorder = [1]
**Output:** [1]

**Constraints:**

* `1 <= preorder.length <= 30`
* `1 <= preorder[i] <= preorder.length`
* All the values of `preorder` are **unique**.
* `postorder.length == preorder.length`
* `1 <= postorder[i] <= postorder.length`
* All the values of `postorder` are **unique**.
* It is guaranteed that `preorder` and `postorder` are the preorder traversal and postorder traversal of the same binary tree.

# Approaches
## Recursive Approach with Array Slicing
This approach directly translates the properties of preorder and postorder traversals into a recursive algorithm. It identifies the root and then determines the bounds of the left and right subtrees by finding the left child's root in the postorder array. It then creates new sub-arrays for the left and right subtrees and calls itself recursively. While conceptually straightforward, this method is highly inefficient due to the overhead of creating array slices in each step.
**Time:** O(N^2), where N is the number of nodes. For each node, we might scan a significant portion of the `postorder` array and create new sub-arrays, both of which are O(N) operations. This leads to a quadratic time complexity. · **Space:** O(N^2), where N is the number of nodes. The recursion depth can be O(N), and at each level, new arrays are created, leading to a quadratic space complexity in the worst case.
**Pros:** Easy to understand and implement.; Directly follows the definitions of the traversals.
**Cons:** Very inefficient in both time and space.; Creating new array slices in every recursive call leads to high memory usage and overhead.
### Explanation
The fundamental idea relies on the traversal orders:
- **Preorder:** `Root -> Left -> Right`
- **Postorder:** `Left -> Right -> Root`

From this, we know that `preorder[0]` is the root of the current tree. If the tree is not just a single node, `preorder[1]` must be the root of the left subtree. We can then find this value (`preorder[1]`) in the `postorder` array. All elements in the `postorder` array up to and including this value belong to the left subtree. This allows us to determine the size of the left subtree.

Once we know the size of the left subtree, we can partition both the `preorder` and `postorder` arrays into three parts: the root, the left subtree's elements, and the right subtree's elements. We then make recursive calls on these smaller, newly created sub-arrays to build the left and right children of the root.

```java
import java.util.Arrays;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        if (preorder.length == 1) {
            return root;
        }

        int leftRootVal = preorder[1];
        int leftSubtreeSize = 0;
        for (int i = 0; i < postorder.length; i++) {
            if (postorder[i] == leftRootVal) {
                leftSubtreeSize = i + 1;
                break;
            }
        }

        root.left = constructFromPrePost(
            Arrays.copyOfRange(preorder, 1, 1 + leftSubtreeSize),
            Arrays.copyOfRange(postorder, 0, leftSubtreeSize)
        );

        if (preorder.length > 1 + leftSubtreeSize) {
            root.right = constructFromPrePost(
                Arrays.copyOfRange(preorder, 1 + leftSubtreeSize, preorder.length),
                Arrays.copyOfRange(postorder, leftSubtreeSize, postorder.length - 1)
            );
        }

        return root;
    }
}
```
### Algorithm
- Create a recursive function `construct(pre, post)`.
- **Base Case:** If the `pre` array is empty, return `null`.
- Create a `TreeNode` for the root using `pre[0]`.
- If `pre` has only one element, return the root node as it's a leaf.
- Identify the root of the left subtree, which is `pre[1]`.
- Linearly scan the `post` array to find the index of the left subtree's root. Let this be `postIdx`.
- The number of nodes in the left subtree is `leftSubtreeSize = postIdx + 1`.
- Create new arrays (slices) for the left and right subtrees from the `pre` and `post` arrays.
  - Left subtree `preorder`: `pre.slice(1, 1 + leftSubtreeSize)`
  - Left subtree `postorder`: `post.slice(0, leftSubtreeSize)`
  - Right subtree `preorder`: `pre.slice(1 + leftSubtreeSize, pre.length)`
  - Right subtree `postorder`: `post.slice(leftSubtreeSize, post.length - 1)`
- Recursively call `construct` for the left and right subtrees and assign them to `root.left` and `root.right`.
- Return the `root`.

## Recursive Approach with Indices
This approach improves upon the previous one by eliminating the costly array slicing operations. Instead of creating new arrays for each recursive call, we pass indices that define the current working segments of the original `preorder` and `postorder` arrays. This significantly reduces memory usage and improves performance, but the time complexity remains quadratic because we still need to linearly scan the `postorder` array segment to find the boundary of the left subtree.
**Time:** O(N^2). The linear scan to find the left subtree's root in the `postorder` array segment is performed for each of the N nodes, resulting in a quadratic time complexity. · **Space:** O(N) for the recursion stack. In the worst case of a skewed tree, the recursion depth can be N.
**Pros:** More space-efficient than the array slicing method.; Avoids the overhead of object creation for new arrays.
**Cons:** The time complexity is still O(N^2) due to the linear scan in each recursive call.; Not efficient for large trees.
### Explanation
To avoid the overhead of creating new arrays, we can define a recursive helper function that takes the start and end indices for the current subproblems in the `preorder` and `postorder` arrays. The logic for identifying the root, the left subtree's root, and the size of the subtrees remains identical to the first approach. The key difference is that instead of slicing, we calculate the new index boundaries for the recursive calls for the left and right children. This optimization improves space complexity from O(N^2) to O(N).

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        return build(preorder, 0, preorder.length - 1, postorder, 0, postorder.length - 1);
    }

    private TreeNode build(int[] pre, int preStart, int preEnd, int[] post, int postStart, int postEnd) {
        if (preStart > preEnd) {
            return null;
        }

        TreeNode root = new TreeNode(pre[preStart]);
        if (preStart == preEnd) {
            return root;
        }

        int leftRootVal = pre[preStart + 1];
        int postIdx = -1;
        for (int i = postStart; i <= postEnd; i++) {
            if (post[i] == leftRootVal) {
                postIdx = i;
                break;
            }
        }

        int leftSubtreeSize = postIdx - postStart + 1;

        root.left = build(pre, preStart + 1, preStart + leftSubtreeSize, post, postStart, postIdx);
        root.right = build(pre, preStart + leftSubtreeSize + 1, preEnd, post, postIdx + 1, postEnd - 1);

        return root;
    }
}
```
### Algorithm
- Create a helper recursive function `build(preStart, preEnd, postStart, postEnd)` that operates on indices of the original arrays.
- **Base Case:** If `preStart > preEnd`, the current segment is empty, so return `null`.
- Create a `TreeNode` for the root using `preorder[preStart]`.
- If `preStart == preEnd`, it's a leaf node, so return it.
- Identify the left subtree's root value: `leftRootVal = preorder[preStart + 1]`.
- Linearly scan the `postorder` array from `postStart` to `postEnd` to find the index of `leftRootVal`. Let this be `postIdx`.
- Calculate the number of nodes in the left subtree: `leftSubtreeSize = postIdx - postStart + 1`.
- Make a recursive call to build the left subtree with updated indices:
  `build(preStart + 1, preStart + leftSubtreeSize, postStart, postIdx)`.
- Make a recursive call to build the right subtree with updated indices:
  `build(preStart + leftSubtreeSize + 1, preEnd, postIdx + 1, postEnd - 1)`.
- Return the `root`.

## Optimized Recursive Approach with a Map
This is the most efficient approach. It optimizes the index-based recursive solution by eliminating the O(N) search in each step. By pre-processing the `postorder` array into a hash map, we can find the index of any element in O(1) time. This reduces the work done at each recursive step to constant time, leading to an overall linear time complexity for constructing the entire tree.
**Time:** O(N). Building the hash map takes O(N). The recursive function is called N times, with each call performing O(1) work (thanks to the map). · **Space:** O(N). We use O(N) space for the hash map and O(N) for the recursion stack in the worst case.
**Pros:** Optimal time complexity of O(N).; It's a common and powerful pattern for solving tree construction problems from traversals.
**Cons:** Requires O(N) extra space for the hash map.
### Explanation
The bottleneck in the previous approach was the repeated linear search to locate the root of the left subtree within the `postorder` array. We can eliminate this by pre-calculating the positions of all values. We first iterate through the `postorder` array and store each element's value and its index in a `HashMap`. 

Now, inside our recursive function, when we need to find the index of the left subtree's root (`preorder[preStart + 1]`), we can simply look it up in our map. This is an O(1) operation. Since every other operation within a single recursive call is also O(1), and the function is called once for each node, the total time complexity becomes O(N).

```java
import java.util.HashMap;
import java.util.Map;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private Map<Integer, Integer> postorderMap;
    private int[] preorder;
    private int[] postorder;

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        this.preorder = preorder;
        this.postorder = postorder;
        this.postorderMap = new HashMap<>();
        for (int i = 0; i < postorder.length; i++) {
            postorderMap.put(postorder[i], i);
        }
        return build(0, preorder.length - 1, 0, postorder.length - 1);
    }

    private TreeNode build(int preStart, int preEnd, int postStart, int postEnd) {
        if (preStart > preEnd) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[preStart]);
        if (preStart == preEnd) {
            return root;
        }

        int leftRootVal = preorder[preStart + 1];
        int postIdx = postorderMap.get(leftRootVal);
        
        int leftSubtreeSize = postIdx - postStart + 1;

        root.left = build(preStart + 1, preStart + leftSubtreeSize, postStart, postIdx);
        root.right = build(preStart + leftSubtreeSize + 1, preEnd, postIdx + 1, postEnd - 1);

        return root;
    }
}
```
### Algorithm
- Before recursion, create a `HashMap` to store the mapping of each value in `postorder` to its index. This takes O(N) time.
- Use the same recursive helper function `build(preStart, preEnd, postStart, postEnd)` as in the previous approach.
- **Base Case:** If `preStart > preEnd`, return `null`.
- Create a `TreeNode` for the root using `preorder[preStart]`.
- If `preStart == preEnd`, return the root.
- Identify the left subtree's root value: `leftRootVal = preorder[preStart + 1]`.
- Instead of a linear scan, use the pre-computed `HashMap` to find the index of `leftRootVal` in `postorder` in O(1) time. Let this be `postIdx`.
- Calculate the size of the left subtree: `leftSubtreeSize = postIdx - postStart + 1`.
- Make recursive calls for the left and right subtrees with the calculated index boundaries, just like in the previous approach.
- Return the `root`.

# Solutions
### Java

```java
public class Construct_Binary_Tree_from_Preorder_and_Postorder_Traversal { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { /* preorder -> [1] [2,4,5] [3,6,7] postorder -> [4,5,2] [6,7,3] [root] */ public TreeNode constructFromPrePost ( int [] pre , int [] post ) { return helper ( pre , 0 , pre . length - 1 , post , 0 , post . length - 1 ); } // preL 和 preR 分别表示左子树区间的开头和结尾位置 // postL 和 postR 表示右子树区间的开头和结尾位置 TreeNode helper ( int [] pre , int preL , int preR , int [] post , int postL , int postR ) { if ( preL > preR || postL > postR ) { return null ; } // root node TreeNode node = new TreeNode ( pre [ preL ]); if ( preL == preR ) { // leaf node return node ; } // 找左子树的根结点(pre[preL + 1) 在 post[] 中的位置 // pre[preL + 1 here "+1" to skip above root node int idx = - 1 ; for ( idx = postL ; idx <= postR ; ++ idx ) { if ( pre [ preL + 1 ] == post [ idx ]) { break ; } } // left sub tree length: (idx - postL) // right sub tree length: node . left = helper ( pre , preL + 1 , preL + 1 + ( idx - postL ), post , postL , idx ); node . right = helper ( pre , preL + 1 + ( idx - postL ) + 1 , preR , post , idx + 1 , postR - 1 ); // postR - 1 to skip root return node ; } } } ////// class Solution { public TreeNode constructFromPrePost ( int [] pre , int [] post ) { int length = pre . length ; if ( length == 0 ) return null ; else if ( length == 1 ) return new TreeNode ( pre [ 0 ]); else { TreeNode root = new TreeNode ( pre [ 0 ]); int leftChild = pre [ 1 ]; int leftCount = 0 ; for ( int i = 0 ; i < length ; i ++) { if ( post [ i ] == leftChild ) { leftCount = i + 1 ; break ; } } root . left = constructFromPrePost ( Arrays . copyOfRange ( pre , 1 , 1 + leftCount ), Arrays . copyOfRange ( post , 0 , leftCount )); root . right = constructFromPrePost ( Arrays . copyOfRange ( pre , 1 + leftCount , length ), Arrays . copyOfRange ( post , leftCount , length - 1 )); return root ; } } }
```

### Python

```python
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None ''' >>> a = [1,2,3,4,5] >>> a[0:2] [1, 2] so right index is exclusive ''' class Solution ( object ): def constructFromPrePost ( self , pre , post ): """ :type pre: List[int] :type post: List[int] :rtype: TreeNode """ if not pre or not post : return None root = TreeNode ( pre [ 0 ]) if len ( pre ) == 1 : return root idx = pre . index ( post [ - 2 ]) root . left = self . constructFromPrePost ( pre [ 1 : idx ], post [: idx - 1 ]) root . right = self . constructFromPrePost ( pre [ idx :], post [ idx - 1 : - 1 ]) return root ############ # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def constructFromPrePost ( self , preorder : List [ int ], postorder : List [ int ] ) -> TreeNode : n = len ( preorder ) if n == 0 : return None root = TreeNode ( preorder [ 0 ]) if n == 1 : return root for i in range ( n - 1 ): if postorder [ i ] == preorder [ 1 ]: root . left = self . constructFromPrePost ( preorder [ 1 : 1 + i + 1 ], postorder [: i + 1 ] ) root . right = self . constructFromPrePost ( preorder [ 1 + i + 1 :], postorder [ i + 1 : - 1 ] ) return root
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/ // Time: O(N^2) // Space: O(N) class Solution { private: TreeNode * construct ( vector < int > & pre , int preBegin , int preEnd , vector < int > & post , int postBegin , int postEnd ) { if ( preBegin >= preEnd ) return NULL ; auto node = new TreeNode ( pre [ preBegin ]); if ( preBegin + 1 < preEnd ) { int leftVal = pre [ preBegin + 1 ]; int postMid = find ( post . begin () + postBegin , post . begin () + postEnd - 1 , leftVal ) - post . begin (); int postLeftLength = postMid - postBegin + 1 ; node -> left = construct ( pre , preBegin + 1 , preBegin + 1 + postLeftLength , post , postBegin , postMid + 1 ); node -> right = construct ( pre , preBegin + 1 + postLeftLength , preEnd , post , postMid + 1 , postEnd - 1 ); } return node ; } public: TreeNode * constructFromPrePost ( vector < int >& pre , vector < int >& post ) { return construct ( pre , 0 , pre . size (), post , 0 , post . size ()); } };
```