889. Construct Binary Tree from Preorder and Postorder Traversal

MediumTreeArrayHash TableDivide and ConquerBinary Tree

Problem Description

The problem requires the construction of a binary tree from two given lists of integers: one representing the preorder traversal and the other the postorder traversal of that binary tree. We are told that the binary tree is made up of distinct values, which is important as it ensures that each value uniquely identifies a node.

The preorder traversal is a list of node values we get if we visit nodes in the following order: visit the root node, then recursively visit the left subtree, and finally the right subtree. The postorder traversal visits nodes in a different order: first the left subtree, then the right subtree, and finally the root node.

Given these two traversal sequences, the task is to reconstruct the original binary tree. It is possible that more than one binary tree could fit the given traversals, and if that's the case, we are allowed to return any valid binary tree.

Intuition

Understanding the traversal orders is key to solving this problem.

Preorder traversal always starts with the root node. So, the first element in the preorder list is the root of the tree.
Postorder traversal ends with the root node. So, the last element in the postorder list is the root of the tree.

Knowing the unique property of the elements in the tree, we can use this information to split the preorder and postorder lists into sublists that describe the left and right subtrees. Here's the general approach:

Create the root node of the tree using the first element from the preorder list.
Locate the root of the left subtree. It's the second element in the preorder list because after the root, preorder visits the left subtree.
In the postorder list, find the position of this left subtree's root. Everything before this position corresponds to the nodes of the left subtree.
The elements from the second position up to (and not including) the located position of the left subtree's root in the preorder list describe the nodes for the left subtree. Similarly, the first few elements in the postorder list, up to the position of the left subtree's root, also describe nodes for the left subtree.
Everything to the right of the located left subtree's root in both lists refers to the right subtree.
With these identified sublists, we recursively call the function to create left and right subtrees.
Once both subtrees are created, attach them to the root, and return the constructed binary tree.

By continuously applying this approach, we can reconstruct the entirety of the binary tree from just its preorder and postorder traversals.

Learn more about Tree, Divide and Conquer and Binary Tree patterns.

Solution Approach

The code implements the intuition described previously into a concrete algorithm that recursively constructs the binary tree. Here is a step-by-step walkthrough of the implementation:

Base Case: If the list preorder is empty, the function returns None because an empty traversal indicates an empty tree or subtree.
The root node of the current (sub)tree is always the first element of the preorder list, as per the definition of preorder traversal. The code creates a new TreeNode with that value.
Another Base Case: If the preorder list contains only one element, then the tree is just a single node. In this case, the function returns this node as both the preorder and postorder will have the same single element.
Recursive Case: To build the left and right subtrees, the code first needs to find the divide point, which is the index of the left subtree's root in postorder. Since the second element of preorder is always the root of the left subtree, it uses a loop to find where this element appears in postorder. This index determines the divide between the left and right subtrees in the postorder list.
Once the divide is found, the code slices the preorder and postorder lists accordingly to form two new pairs of lists: one pair for the left subtree (preorder[1: 1 + i + 1], postorder[:i + 1]) and another pair for the right subtree (preorder[1 + i + 1:], postorder[i + 1: -1]). The slicing of the lists is done so that the elements that belong to the left subtree in both traversals are grouped together, and the same goes for the right subtree.
The code then recursively calls constructFromPrePost on the left sublist pair to construct the left subtree, and stores this as the left child of the root. Similarly, it recursively calls constructFromPrePost on the right sublist pair to construct the right subtree, and stores this as the right child of the root.
The recursion ensures that the entire tree is constructed by breaking down the tree into smaller subtrees and constructing them piece by piece.
After constructing the left and right subtrees, they are attached to the root, and the root node is then returned, which combines the subtrees into the larger tree that is being put together piece by piece.

By executing this algorithm, we can fully reconstruct the original binary tree from preorder and postorder traversals, even though there might be more than one binary tree that fits the given preorder and postorder traversals. However, the code only needs to return any one of them.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach. Consider the following preorder and postorder traversal lists of a binary tree:

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

Using these two lists, we will walk through the construction of the binary tree step by step:

The first element from the preorder list is 1, which is the root node of the tree.
The second element in the preorder list is 2, which is the root of the left subtree.
We find 2 in the postorder list at position 2. The elements before that (4, 5) are the left subtree's postorder.
For the left subtree: preorder sublist is [2, 4, 5] (skipping the first element 1 which is the root), and the postorder sublist is [4, 5, 2].

For the right subtree: we take the remaining elements, preorder sublist [3, 6, 7] and postorder sublist [6, 7, 3].
Now, we will recursively construct the left subtree. The first element 2 becomes the root of the left subtree.

Next, we look for 4 (second element of left preorder sublist) in the left postorder sublist. We find it at position 0. This means 4 is a leaf node, and similarly, 5 is a leaf node by the same process.
We repeat the process for the right subtree. The first element 3 is the root. We look for 6 and 7 in the right postorder sublist and discover they are consecutive leaf nodes.
We attach the constructed left subtree (2) with nodes 4 and 5 as leaf children, and right subtree (3) with nodes 6 and 7 as leaf children, to the root node 1.
The recursion continues until all nodes are placed correctly with their respective children, and we obtain the final binary tree.

By following the steps of the recursion according to the preorder and postorder lists, we've successfully rebuilt the binary tree:

This walkthrough exemplifies the steps involved in reconstructing a binary tree from preorder and postorder traversal lists. The resulting structure adheres to the sequences provided while also fulfilling the properties of a binary tree.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> TreeNode:
10        # Get the number of nodes in the tree from the length of preorder list.
11        node_count = len(preorder)
12      
13        # If the tree is empty, return None.
14        if node_count == 0:
15            return None
16          
17        # The first element from the preorder list is always the root node.
18        root = TreeNode(preorder[0])
19      
20        # If the tree only has one node, return it as the root.
21        if node_count == 1:
22            return root
23      
24        # Iterate through the postorder list to find the root of left subtree.
25        for i in range(node_count - 1):
26            # Preorder[1] would be the root of the left subtree if such exists.
27            if postorder[i] == preorder[1]:
28                # Using the found index, divide preorder & postorder lists
29                # to construct the left subtree.
30                root.left = self.constructFromPrePost(
31                    preorder[1: 1 + i + 1], postorder[:i + 1]
32                )
33              
34                # The remaining elements in preorder & postorder lists
35                # are used to construct the right subtree.
36                root.right = self.constructFromPrePost(
37                    preorder[1 + i + 1:], postorder[i + 1: -1]
38                )
39              
40                # Return the constructed binary tree root.
41                return root
42

1import java.util.HashMap;
2import java.util.Map;
3
4// Definition for a binary tree node.
5class TreeNode {
6    int val;                // Node's value.
7    TreeNode left;          // Pointer to the left child node.
8    TreeNode right;         // Pointer to the right child node.
9
10    // Constructor with no parameters initializes val to 0 and all pointers to null.
11    TreeNode() {
12        val = 0;
13        left = null;
14        right = null;
15    }
16
17    // Constructor with the node's value that initializes all pointers to null.
18    TreeNode(int x) {
19        val = x;
20        left = null;
21        right = null;
22    }
23
24    // Constructor with the node's value and pointers to the left and right child nodes.
25    TreeNode(int x, TreeNode left, TreeNode right) {
26        val = x;
27        this.left = left;
28        this.right = right;
29    }
30}
31
32class Solution {
33    // Map to store the index of each value in postorder traversal.
34    private Map<Integer, Integer> postOrderIndexMap = new HashMap<>();
35
36    // Function that constructs the binary tree from preorder and postorder traversal arrays.
37    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
38        // Fill the map with the postorder values and their indices.
39        for (int i = 0; i < postorder.length; i++) {
40            postOrderIndexMap.put(postorder[i], i);
41        }
42        // Call the recursive build function to construct the tree.
43        return buildTree(preorder, 0, preorder.length - 1, postorder, 0, postorder.length - 1);
44    }
45
46    // Helper function to recursively build the binary tree from preorder and postorder traversal subsets.
47    private TreeNode buildTree(int[] preorder, int preStart, int preEnd,
48                               int[] postorder, int postStart, int postEnd) {
49        // If there are no elements to construct the tree, return null.
50        if (preStart > preEnd) return null;
51
52        // The first value in preorder is the root node value.
53        TreeNode root = new TreeNode(preorder[preStart]);
54
55        // If there is only one node, it is the root of the current subtree.
56        if (preStart == preEnd) return root;
57
58        // Find the index of the root of the left subtree in postorder traversal using the map.
59        int leftRootIndex = postOrderIndexMap.get(preorder[preStart + 1]);
60
61        // The length of the left subtree in the postorder array can be calculated from the indices.
62        int leftSubtreeLength = leftRootIndex - postStart + 1;
63
64        // Recursively construct the left subtree.
65        root.left = buildTree(preorder, preStart + 1, preStart + leftSubtreeLength,
66                              postorder, postStart, leftRootIndex);
67
68        // Recursively construct the right subtree.
69        root.right = buildTree(preorder, preStart + leftSubtreeLength + 1, preEnd,
70                               postorder, leftRootIndex + 1, postEnd - 1);
71
72        // Return the root of the constructed subtree.
73        return root;
74    }
75}
76

1#include <vector>
2#include <unordered_map>
3
4// Definition for a binary tree node.
5struct TreeNode {
6    int val;                // Node's value.
7    TreeNode *left;         // Pointer to the left child node.
8    TreeNode *right;        // Pointer to the right child node.
9
10    // Constructor with no parameters initializes val to 0 and all pointers to nullptr.
11    TreeNode() : val(0), left(nullptr), right(nullptr) {}
12
13    // Constructor with the node's value that initializes all pointers to nullptr.
14    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
15
16    // Constructor with the node's value and pointers to the left and right child nodes.
17    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
18};
19
20class Solution {
21public:
22    std::unordered_map<int, int> postOrderIndexMap;    // Map to store the index of each value in postorder.
23
24    // Function that constructs the binary tree from preorder and postorder traversal vectors.
25    TreeNode* constructFromPrePost(std::vector<int>& preorder, std::vector<int>& postorder) {
26        // Fill the map with the postorder values and their indices.
27        for (int i = 0; i < postorder.size(); ++i) {
28            postOrderIndexMap[postorder[i]] = i;
29        }
30        // Call the recursive build function to construct the tree.
31        return buildTree(preorder, 0, preorder.size() - 1, postorder, 0, postorder.size() - 1);
32    }
33
34private:
35    // Helper function to recursively build the binary tree from preorder and postorder traversal subsets.
36    TreeNode* buildTree(std::vector<int>& preorder, int preStart, int preEnd,
37                        std::vector<int>& postorder, int postStart, int postEnd) {
38        // If there are no elements to construct the tree, return nullptr.
39        if (preStart > preEnd) return nullptr;
40
41        // The first value in preorder is the root node value.
42        TreeNode* root = new TreeNode(preorder[preStart]);
43
44        // If there is only one node, it is the root of the current subtree.
45        if (preStart == preEnd) return root;
46
47        // Find the index of the root of the left subtree in postorder traversal using the map.
48        int leftRootIndex = postOrderIndexMap[preorder[preStart + 1]];
49      
50        // The length of the left subtree in the postorder array can be calculated from the indices.
51        int leftSubtreeLength = leftRootIndex - postStart + 1;
52
53        // Recursively construct the left subtree.
54        root->left = buildTree(preorder, preStart + 1, preStart + leftSubtreeLength,
55                               postorder, postStart, leftRootIndex);
56
57        // Recursively construct the right subtree.
58        root->right = buildTree(preorder, preStart + leftSubtreeLength + 1, preEnd,
59                                postorder, leftRootIndex + 1, postEnd - 1);
60
61        // Return the root of the constructed subtree.
62        return root;
63    }
64};
65

1interface TreeNode {
2  val: number;
3  left: TreeNode | null;
4  right: TreeNode | null;
5}
6
7// Function to create a new binary tree node with default left and right children as null
8function createTreeNode(val: number, left: TreeNode | null = null, right: TreeNode | null = null): TreeNode {
9  return {
10    val,
11    left,
12    right,
13  };
14}
15
16// Global variable to store the index of each value in the postorder traversal
17const postOrderIndexMap: { [key: number]: number } = {};
18
19// Function that constructs the binary tree from preorder and postorder traversal vectors
20function constructFromPrePost(preorder: number[], postorder: number[]): TreeNode | null {
21  // Fill the map with the postorder values and their indices
22  postorder.forEach((value, index) => {
23    postOrderIndexMap[value] = index;
24  });
25  // Call the recursive build function to construct the tree
26  return buildTree(preorder, 0, preorder.length - 1, postorder, 0, postorder.length - 1);
27}
28
29// Helper function to recursively build the binary tree from preorder and postorder traversal subsets
30function buildTree(
31  preorder: number[],
32  preStart: number,
33  preEnd: number,
34  postorder: number[],
35  postStart: number,
36  postEnd: number
37): TreeNode | null {
38  // If there are no elements to construct the tree, return null
39  if (preStart > preEnd) return null;
40
41  // The first value in preorder is the root node value
42  const root = createTreeNode(preorder[preStart]);
43
44  // If there is only one node, it is the root of the current subtree
45  if (preStart === preEnd) return root;
46
47  // Find the index of the root of the left subtree in postorder traversal using the map
48  const leftRootIndex = postOrderIndexMap[preorder[preStart + 1]];
49
50  // The length of the left subtree in the postorder array can be calculated from the indices
51  const leftSubtreeLength = leftRootIndex - postStart + 1;
52
53  // Recursively construct the left subtree
54  root.left = buildTree(
55    preorder,
56    preStart + 1,
57    preStart + leftSubtreeLength,
58    postorder,
59    postStart,
60    leftRootIndex
61  );
62
63  // Recursively construct the right subtree
64  root.right = buildTree(
65    preorder,
66    preStart + leftSubtreeLength + 1,
67    preEnd,
68    postorder,
69    leftRootIndex + 1,
70    postEnd - 1
71  );
72
73  // Return the root of the constructed subtree
74  return root;
75}
76

Time and Space Complexity

Time Complexity

The given code has a time complexity of O(n^2). This is because the algorithm involves a recursive function that iterates over the postorder array in each recursive call to find the root of the left subtree, which corresponds to preorder[1]. In the worst case, this results in examining each element in postorder for each recursive call, which leads to O(n) operations per call. Since there are n recursive calls made in the process of constructing the tree, the time complexity becomes O(n * n) = O(n^2).

Space Complexity

The space complexity of the code is O(n) due to the recursive nature of the function call stack. In the worst case, the binary tree could be completely unbalanced, resembling a linked list, which would result in O(n) recursive calls, and therefore O(n) space used on the call stack. Additionally, space is allocated for the sliced lists in preorder and postorder arguments in the recursive calls. However, since this does not create new lists but rather creates references to the existing list portions, it does not contribute significantly to the space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don't know