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.

Examples

Example 1:

graph TD;
	A(1)
	B(2)
	C(3)
	D(4)
	E(5)
	F(6)
	G(7)

	A --- B & C
	B --- D & E
	C --- F & G
  
1
2

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:

1
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.

Solution

Method 1 - Recursion without hashmap

To reconstruct a binary tree given its preorder and postorder traversal arrays, we rely on the following observations:

  • In preorder traversal: The root of a subtree appears first, then the left subtree elements, followed by the right subtree elements.
  • In postorder traversal: The elements of the left subtree come first, followed by those of the right subtree, and finally the root.

We will use recursion to construct the tree.

  • In preorder, the first element is always the root of the tree/subtree.
  • In postorder, the last element is always the root of the tree/subtree.
  • We determine the left and right subtrees by breaking the arrays appropriately:
    • Use the element order in preorder to find the left child (the second element in preorder).
    • Locate the left child in postorder to determine the boundary of the left subtree.

Here are the steps:

  • Start by identifying the root (first element of preorder).
  • If there’s more than one element in the traversal arrays:
    • Identify the left child from the second element of preorder.
    • Locate this left child in postorder to divide into left and right subtrees.
  • Recursively build the left and right subtrees by diving into smaller segments of preorder and postorder.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        return build(preorder, postorder, 0, preorder.length - 1, 0, postorder.length - 1);
    }
    
    private TreeNode build(int[] pre, int[] post, int preStart, int preEnd, int postStart, int postEnd) {
        if (preStart > preEnd || postStart > postEnd) {
            return null;
        }
        
        TreeNode root = new TreeNode(pre[preStart]); // Root is the first element in preorder
        if (preStart == preEnd) {
            return root; // Single-node tree
        }
        
        // Find the left subtree boundary
        int leftRootVal = pre[preStart + 1];
        int idx = postStart;
        while (post[idx] != leftRootVal) {
            idx++;
        }
        
        // Calculate sizes of left and right subtrees
        int leftSize = idx - postStart + 1;
        
        // Recursively build left and right subtrees
        root.left = build(pre, post, preStart + 1, preStart + leftSize, postStart, idx);
        root.right = build(pre, post, preStart + leftSize + 1, preEnd, idx + 1, postEnd - 1);
        
        return root;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not preorder or not postorder:
            return None
        
        root = TreeNode(preorder[0])  # Root is the first element in preorder
        if len(preorder) == 1:
            return root  # Single-node tree
        
        # Find the left subtree boundary
        left_root_val = preorder[1]
        idx = postorder.index(left_root_val)
        
        # Divide preorder and postorder into left and right subtrees
        root.left = self.constructFromPrePost(preorder[1:idx + 2], postorder[:idx + 1])
        root.right = self.constructFromPrePost(preorder[idx + 2:], postorder[idx + 1:-1])
        
        return root

Complexity

  • ⏰ Time complexity: O(n^2), as we recursively divide the arrays
    • Locating the boundary of the left subtree requires O(n) to find an element in postorder (in the worst case for each call).
    • There are n recursive calls as we divide the arrays.
    • Overall time complexity is O(n^2) in the worst case due to the linear search.
  • 🧺 Space complexity: O(n)
    • Recursion uses space O(h), where h is the height of the tree, due to recursion depth, which is proportional to the height of the tree. Which is O(n) in the worst case (skewed tree).
    • O(n) is also used for storing the result

Method 2 - Recursion with hashmap

To speed up previous method, we can use the hashmap to store the indices of values from postorder.This way, we quickly locate the left subtree’s root (based on the second element in preorder) in (O(1)) time.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    private HashMap<Integer, Integer> postIndexMap;

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        // Build a HashMap for quick index lookup in postorder
        postIndexMap = new HashMap<>();
        for (int i = 0; i < postorder.length; i++) {
            postIndexMap.put(postorder[i], i);
        }

        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 || postStart > postEnd) {
            return null;
        }

        TreeNode root = new TreeNode(pre[preStart]); // Root is the first element in preorder
        if (preStart == preEnd) {
            return root; // Single-node tree
        }

        // Find left subtree boundary using the pre[preStart + 1] value in postorder
        int leftRootVal = pre[preStart + 1];
        int idx = postIndexMap.get(leftRootVal);

        // Calculate sizes of left and right subtrees
        int leftSize = idx - postStart + 1;

        // Recursively build left and right subtrees
        root.left = build(pre, preStart + 1, preStart + leftSize, post, postStart, idx);
        root.right = build(pre, preStart + leftSize + 1, preEnd, post, idx + 1, postEnd - 1);

        return root;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        # Build a dictionary for quick index lookup in postorder
        post_index_map = {val: idx for idx, val in enumerate(postorder)}

        def build(preStart: int, preEnd: int, postStart: int, postEnd: int) -> Optional[TreeNode]:
            if preStart > preEnd or postStart > postEnd:
                return None
            
            root = TreeNode(preorder[preStart])  # Root is the first element in preorder
            if preStart == preEnd:
                return root  # Single-node tree

            # Find left subtree boundary using the preorder[preStart + 1] value in postorder
            left_root_val = preorder[preStart + 1]
            idx = post_index_map[left_root_val]

            # Calculate sizes of left and right subtrees
            left_size = idx - postStart + 1

            # Recursively build left and right subtrees
            root.left = build(preStart + 1, preStart + left_size, postStart, idx)
            root.right = build(preStart + left_size + 1, preEnd, idx + 1, postEnd - 1)

            return root

        return build(0, len(preorder) - 1, 0, len(postorder) - 1)

Complexity

  • ⏰ Time complexity: O(n)
    • Constructing the HashMap takes (O(n)).
    • Recursive tree construction performs (O(n)) operations since each recursive layer processes nodes from preorder and postorder once.
    • Overall time complexity: O(n)
  • 🧺 Space complexity: O(n)
    • HashMap for postorder indices: (O(n)).
    • Recursive Stack: For a skewed tree, the recursion depth could reach (O(n)).
    • Total space complexity: O(n)