#889

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Construct Binary Tree from Preorder and Postorder Traversal

Reconstruct a binary tree from preorder and postorder traversals using array scanning and hash lookup.

array hash table divide and conquer tree binary tree

Problem Statement

You are given two integer arrays: preorder and postorder. Preorder represents the preorder traversal of a binary tree, and postorder represents the postorder traversal of the same tree. Your task is to reconstruct and return the binary tree from these traversals. It is guaranteed that the tree can be reconstructed uniquely from the given traversals.

Note that there may be multiple valid solutions, but for this problem, any valid tree is acceptable. The tree will contain distinct values, and the length of the preorder and postorder arrays will be the same, bounded between 1 and 30 elements.

Examples

Example 1

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 details omitted.

Example 2

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

Output: [1]

Example details omitted.

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 Approach

Array Scanning

The key idea is to efficiently scan through the preorder and postorder arrays. By observing that the first element in preorder is always the root, and the last element in postorder is the root as well, we can break down the tree into subtrees. This process involves recursively identifying the left and right subtrees.

Hash Lookup

Using a hash map to store the positions of elements in the preorder or postorder arrays allows for faster lookups. The hash map helps to quickly determine where an element exists in the traversal, which speeds up the process of splitting the tree into left and right subtrees.

Recursive Tree Construction

Using recursion, the tree is built by constructing the left and right subtrees based on the identified root nodes. This recursive approach ensures that every subtree is processed correctly, following the preorder and postorder traversal rules to determine the structure of the binary tree.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Both time and space complexity for this solution are O(n), where n is the number of nodes in the tree. The time complexity arises from the need to traverse the entire tree and perform hash lookups. The space complexity is mainly due to the hash map and recursion stack used during the construction process.

What Interviewers Usually Probe

Ability to handle recursive problems efficiently.
Understanding of hash maps and their applications in tree construction.
Proficiency in managing multiple traversal patterns in binary trees.

Common Pitfalls or Variants

Common pitfalls

Not correctly handling recursive base cases, leading to incorrect tree construction.
Misunderstanding how to split the preorder and postorder arrays into subtrees.
Inefficient lookup or missing hash map optimization for faster element positions.

Follow-up variants

Consider cases with trees containing only one node.
Explore variations with non-distinct values in the arrays.
Test the algorithm with the maximum allowed input size (30 nodes).

FAQ

What is the main approach to solving Construct Binary Tree from Preorder and Postorder Traversal?

The main approach is to use array scanning combined with hash lookups to reconstruct the binary tree from the given traversals.

How do hash maps help in solving Construct Binary Tree from Preorder and Postorder Traversal?

Hash maps speed up the process by allowing fast lookups to identify where elements appear in the preorder and postorder arrays, which is crucial for constructing subtrees.

What are the time and space complexities of the Construct Binary Tree from Preorder and Postorder Traversal solution?

Both time and space complexity are O(n), where n is the number of nodes in the binary tree.

What are common pitfalls in solving Construct Binary Tree from Preorder and Postorder Traversal?

Common pitfalls include incorrect handling of recursive base cases, inefficient array splitting, and poor hash map utilization for fast lookups.

How can GhostInterview help with Construct Binary Tree from Preorder and Postorder Traversal?

GhostInterview helps by providing a structured approach to practicing the algorithm, offering insights into recursive tree construction and optimizing your solution with hash maps.

terminal

Solution

Solution 1: Recursion

The order of pre-order traversal is: root node -> left subtree -> right subtree, and the order of post-order traversal is: left subtree -> right subtree -> root node.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

# 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]
    ) -> Optional[TreeNode]:
        def dfs(a: int, b: int, c: int, d: int) -> Optional[TreeNode]:
            if a > b:
                return None
            root = TreeNode(preorder[a])
            if a == b:
                return root
            i = pos[preorder[a + 1]]
            m = i - c + 1
            root.left = dfs(a + 1, a + m, c, i)
            root.right = dfs(a + m + 1, b, i + 1, d - 1)
            return root

        pos = {x: i for i, x in enumerate(postorder)}
        return dfs(0, len(preorder) - 1, 0, len(postorder) - 1)

Solution 2: Another Recursive Approach

We can design a recursive function $dfs(i, j, n)$, where $i$ and $j$ represent the starting points of the pre-order and post-order traversals, respectively, and $n$ represents the number of nodes. This function constructs the root node of the binary tree based on the pre-order traversal $[i, i + n - 1]$ and post-order traversal $[j, j + n - 1]$. The answer is $dfs(0, 0, n)$, where $n$ is the length of the pre-order traversal.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

# 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]
    ) -> Optional[TreeNode]:
        def dfs(a: int, b: int, c: int, d: int) -> Optional[TreeNode]:
            if a > b:
                return None
            root = TreeNode(preorder[a])
            if a == b:
                return root
            i = pos[preorder[a + 1]]
            m = i - c + 1
            root.left = dfs(a + 1, a + m, c, i)
            root.right = dfs(a + m + 1, b, i + 1, d - 1)
            return root

        pos = {x: i for i, x in enumerate(postorder)}
        return dfs(0, len(preorder) - 1, 0, len(postorder) - 1)

Continue Practicing

#106 construct binary tree from inorder and postorder traversal #105 construct binary tree from preorder and inorder traversal #1110 delete nodes and return forest