889. Construct Binary Tree from Preorder and Postorder Traversal
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 thepostorder
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 returnsNone
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 newTreeNode
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
andpostorder
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 ofpreorder
is always the root of the left subtree, it uses a loop to find where this element appears inpostorder
. 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
andpostorder
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 theleft
child of theroot
. Similarly, it recursively callsconstructFromPrePost
on the right sublist pair to construct the right subtree, and stores this as theright
child of theroot
. -
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 EvaluatorExample 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 is1
, which is the root node of the tree. -
The second element in the
preorder
list is2
, which is the root of the left subtree. -
We find
2
in thepostorder
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 element1
which is the root), and thepostorder
sublist is[4, 5, 2]
.For the right subtree: we take the remaining elements,
preorder
sublist[3, 6, 7]
andpostorder
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 leftpreorder
sublist) in the leftpostorder
sublist. We find it at position 0. This means4
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 for6
and7
in the rightpostorder
sublist and discover they are consecutive leaf nodes. -
We attach the constructed left subtree
(2)
with nodes4
and5
as leaf children, and right subtree(3)
with nodes6
and7
as leaf children, to the root node1
. -
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:
1 1 2 / \ 3 2 3 4 / \ / \ 5 4 5 6 7
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.
Which of the following uses divide and conquer strategy?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger
Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.