106. Construct Binary Tree from Inorder and Postorder Traversal
Problem Description
The given problem involves reconstructing a binary tree from two types of traversal information: the inorder and postorder traversals. In an inorder traversal, you visit the left subtree, the node, and then the right subtree. In a postorder traversal, you visit the left subtree, the right subtree, and then the node itself. The task is to use these two lists, which represent the respective traversals of the binary tree, to recreate the original binary tree structure. It's important to note that each value in the tree is assumed to be unique, which guarantees a unique solution.
Intuition
The key to solving this problem lies in understanding the properties of tree traversals. Postorder traversal gives us the root node at the end of the traversal list, since postorder processes the root after its subtrees. The inorder traversal can then be used to identify which nodes belong to the left and right subtrees. The last element in postorder is certain to be the root of the tree, and once we find this root in the inorder list, we know that all elements to the left of it are part of the left subtree and all elements to the right are part of the right subtree.
To build the tree, we perform the following steps recursively:
- Identify the root node as the last element in the postorder list.
- Find the position of this root in the inorder list to partition it into the left and right subtree nodes.
- Recursively build the left subtree using the left partition of inorder and postorder lists.
- Recursively build the right subtree with the remaining elements (except the last one as it's the root) of postorder and the right partition of the inorder list.
- Repeat this process till all the nodes are processed and the tree is reconstructed.
The elegance of this approach comes from the recursive nature of trees and the ability to partition them into smaller problems (subtrees) that resemble the original problem.
Learn more about Tree, Divide and Conquer and Binary Tree patterns.
Solution Approach
The provided solution follows a recursive approach that uses the information provided by the inorder
and postorder
arrays to reconstruct the binary tree. Here's a breakdown of how the solution works:
-
A helper function
buildTree
is defined that takes two arguments,inorder
andpostorder
, and returns the root node of the binary tree. -
The base case of the recursion is when the
postorder
list is empty, which means that there is no subtree to construct, and henceNone
is returned. -
If the
postorder
list is not empty, the last element ofpostorder
is the root of the tree or subtree that we are currently building. This value is extracted and used to create a newTreeNode
. -
The position of the root element in the
inorder
array is found using theindex
method. This index is crucial as it helps to divide theinorder
list into left and right subtrees for the current root. -
Using the index
i
found, theinorder
list is split into two parts:inorder[:i]
containing the elements of the left subtree,inorder[i+1:]
for the right subtree.
-
The
postorder
list is also split correspondingly into:postorder[:i]
for the left subtree,postorder[i:-1]
(excluding the last element which is the root) for the right subtree.
-
These partitions are then used to recursively call
buildTree
for the left and right subtrees, setting the returned values as the left and right children of the current root node, respectively. -
The recursion continues until all nodes have been processed, and as the call stack unwinds, the full tree is constructed from bottom to top.
-
Finally, the
root
of the reconstructed binary tree is returned from thebuildTree
function.
This solution uses the properties of tree traversal orders, binary tree recursive structure, and array slicing in Python to reconstruct the tree. Here are the key algorithmic points:
- Recursive tree construction,
- Array slicing for dividing the problem into subproblems,
- Finding the root node from the
postorder
traversal and partitioning the lists using it.
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 illustrate the solution approach using a simple example. We'll use a small binary tree and walk through the reconstructions step by step with the given inorder and postorder traversals.
Suppose we have the following binary tree:
3 / \ 9 20 / \ 15 7
The inorder traversal for this tree is [9, 3, 15, 20, 7]
and the postorder traversal is [9, 15, 7, 20, 3]
. We wish to reconstruct the original binary tree from these traversals.
Step 1: We first take the last element from the postorder list, which is 3
. This is the root of the binary tree.
Step 2: We find the position of 3
in the inorder list. The index is 1
. This tells us that all elements to the left of 3
in the inorder list belong to the left subtree, and all elements to the right belong to the right subtree.
Partitioning the lists:
- The inorder left subtree:
[9]
- The inorder right subtree:
[15, 20, 7]
- The postorder left subtree:
[9]
(corresponding to the left partition of inorder list) - The postorder right subtree is everything up to but excluding the root from postorder:
[15, 7, 20]
Step 3: We now recursively build the left subtree with inorder[:1]
and postorder[:1]
and the right subtree with inorder[2:]
and postorder[1:-1]
.
Building the left subtree:
- The postorder list is
[9]
, and its last element,9
, is the root of the left subtree. - Since
9
has no left or right children (as can be inferred from the single element lists), the left subtree is just a single node with value9
.
Building the right subtree:
- The postorder list for the right subtree is
[15, 7, 20]
. The last element,20
, is the root for the right subtree. - We find
20
in the inorder list, which is at index3
(considering0
as the starting index for this sublist[15, 20, 7]
). - Partitioning the lists for the right subtree, we get:
- Inorder left subtree:
[15]
- Inorder right subtree:
[7]
- Postorder left subtree:
[15]
(before20
in postorder list) - Postorder right subtree:
[7]
(before20
in postorder list)
- Inorder left subtree:
Repeating the process for the subtrees of 20
:
-
Subtree with
15
as root:- Since there are no other elements in the postorder and inorder lists, we can infer that
15
has no children.
- Since there are no other elements in the postorder and inorder lists, we can infer that
-
Subtree with
7
as root:- Similarly, as
7
is alone in its postorder and inorder lists, it also has no children.
- Similarly, as
As we complete each recursive step, we assign the newly created nodes as children to their respective parents. And by doing this from bottom to top, we finally recreate the original tree structure:
3 / \ 9 20 / \ 15 7
This example walkthrough captures the essence of the solution approach by recursively building left and right subtrees using the partitions of the inorder and postorder traversal lists.
Solution Implementation
1from typing import List
2
3# Definition for a binary tree node.
4class TreeNode:
5 def __init__(self, value=0, left=None, right=None):
6 self.value = value
7 self.left = left
8 self.right = right
9
10class Solution:
11 def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
12 # If the postorder list is empty, no tree can be constructed
13 if not postorder:
14 return None
15
16 # The last element in the postorder list is the root node value
17 root_value = postorder[-1]
18 # Create the root node with the value
19 root = TreeNode(val=root_value)
20
21 # Find the index of the root value in the inorder list
22 # This index partitions the tree into left and right subtrees
23 index = inorder.index(root_value)
24
25 # Recursively build the left subtree with the left partition of
26 # inorder and postorder slices. The left partition for inorder is
27 # everything before index `i` and for postorder is everything before
28 # the corresponding left subtree size which is also `i` since postorder
29 # and inorder subtrees have the same size when split by the root.
30 root.left = self.buildTree(inorder[:index], postorder[:index])
31
32 # Recursively build the right subtree with the right partition of
33 # inorder (everything after the root) and the corresponding partition
34 # of the postorder list (everything between the left subtree end and
35 # the last element).
36 root.right = self.buildTree(inorder[index + 1 :], postorder[index:-1])
37
38 # Return the constructed binary tree root node
39 return root
40
1class Solution {
2 // Map to store the index of each value present in the inorder array for faster lookups.
3 private Map<Integer, Integer> inorderIndexMap = new HashMap<>();
4
5 // Builds a binary tree from inorder and postorder traversal arrays.
6 public TreeNode buildTree(int[] inorder, int[] postorder) {
7 // Build the index map for quick access during recursive calls
8 for (int i = 0; i < inorder.length; i++) {
9 inorderIndexMap.put(inorder[i], i);
10 }
11 // Call the recursive method starting with the whole range of inorder and postorder arrays
12 return buildTreeRecursive(inorder, postorder, 0, 0, inorder.length);
13 }
14
15 // Recursive method to build the binary tree, using inorder and postorder arrays.
16 private TreeNode buildTreeRecursive(int[] inorder, int[] postorder, int inorderStart, int postorderStart, int length) {
17 // If the current segment is empty, return null because there's no tree to build.
18 if (length <= 0) {
19 return null;
20 }
21
22 // The last node in the postorder segment is the current root.
23 int rootValue = postorder[postorderStart + length - 1];
24 // Get the index of the root value in the inorder array to split left and right subtrees.
25 int inorderRootIndex = inorderIndexMap.get(rootValue);
26
27 // Create the tree node for the value found.
28 TreeNode rootNode = new TreeNode(rootValue);
29
30 // Calculate the number of nodes in the left subtree.
31 int leftSubtreeLength = inorderRootIndex - inorderStart;
32
33 // Recursively build the left subtree.
34 rootNode.left = buildTreeRecursive(inorder, postorder, inorderStart, postorderStart, leftSubtreeLength);
35
36 // Recursively build the right subtree.
37 // Note that the right subtree starts after the left subtree in the postorder array.
38 rootNode.right = buildTreeRecursive(inorder, postorder, inorderRootIndex + 1, postorderStart + leftSubtreeLength, length - leftSubtreeLength - 1);
39
40 // Return the constructed binary tree node.
41 return rootNode;
42 }
43}
44
1#include <unordered_map>
2#include <vector>
3
4// Definition for a binary tree node.
5struct TreeNode {
6 int val;
7 TreeNode *left;
8 TreeNode *right;
9 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15 // Hash table to keep track of the indexes of the elements in the inorder sequence.
16 std::unordered_map<int, int> elementToIndex;
17
18 // Function to build tree from inorder and postorder traversal vectors.
19 TreeNode* buildTree(std::vector<int>& inorder, std::vector<int>& postorder) {
20 // Populate the indexes hash table from the inorder vector.
21 for (int index = 0; index < inorder.size(); ++index) {
22 elementToIndex[inorder[index]] = index;
23 }
24
25 // Recursively construct the binary tree and return its root node.
26 return constructTree(inorder, postorder, 0, 0, inorder.size());
27 }
28
29private:
30 // Recursive function to construct binary tree using inorder and postorder sequences.
31 TreeNode* constructTree(std::vector<int>& inorder, std::vector<int>& postorder, int inorderStart, int postorderStart, int size) {
32 // Base case: when the subtree size is non-positive, it indicates no elements are left for subtree construction.
33 if (size <= 0) return nullptr;
34
35 // Get the root element value for the current subtree from the postorder sequence.
36 int rootValue = postorder[postorderStart + size - 1];
37
38 // Find the index of the root element in the inorder sequence.
39 int rootIndexInInorder = elementToIndex[rootValue];
40
41 // Create root node with the value obtained.
42 TreeNode* root = new TreeNode(rootValue);
43
44 // Recursively build the left subtree.
45 // The left subtree size is determined by the difference between the root index in the inorder
46 // sequence and the current inorder starting index.
47 root->left = constructTree(
48 inorder,
49 postorder,
50 inorderStart,
51 postorderStart,
52 rootIndexInInorder - inorderStart);
53
54 // Recursively build the right subtree.
55 // The right subtree starts immediately after the root index in the inorder sequence.
56 // The size of the right subtree is adjusted to skip the root node.
57 root->right = constructTree(
58 inorder,
59 postorder,
60 rootIndexInInorder + 1,
61 postorderStart + (rootIndexInInorder - inorderStart),
62 size - (rootIndexInInorder - inorderStart + 1));
63
64 return root;
65 }
66};
67
1// Definition for a binary tree node.
2class TreeNode {
3 val: number;
4 left: TreeNode | null;
5 right: TreeNode | null;
6
7 constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 this.val = (val === undefined ? 0 : val);
9 this.left = (left === undefined ? null : left);
10 this.right = (right === undefined ? null : right);
11 }
12}
13
14/**
15 * Reconstructs a binary tree from inorder and postorder traversal arrays.
16 * @param inorder - Inorder traversal of the tree
17 * @param postorder - Postorder traversal of the tree
18 * @returns The root node of the reconstructed binary tree.
19 */
20function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
21 // If the postorder array is empty, the tree cannot be constructed.
22 if (postorder.length === 0) {
23 return null;
24 }
25
26 // The last element in postorder traversal is the root node's value.
27 const rootValue = postorder[postorder.length - 1];
28 // Find the index of the root value in the inorder traversal.
29 const rootIndexInInorder = inorder.indexOf(rootValue);
30
31 // Construct the root node of the tree.
32 const rootNode = new TreeNode(
33 rootValue,
34 // Recursively build the left subtree from the left part of inorder and postorder arrays.
35 buildTree(inorder.slice(0, rootIndexInInorder), postorder.slice(0, rootIndexInInorder)),
36 // Recursively build the right subtree from the right part of inorder and postorder arrays, excluding the last element of postorder.
37 buildTree(inorder.slice(rootIndexInInorder + 1), postorder.slice(rootIndexInInorder, postorder.length - 1))
38 );
39
40 // Return the root node of the reconstructed tree.
41 return rootNode;
42}
43
Time and Space Complexity
Time Complexity:
The time complexity of the provided function can be analyzed based on the operations it performs:
-
The
.index()
operation called on theinorder
list takesO(n)
time each time it is called, since it potentially checks each element in the list to find the index of the root value. -
The
.buildTree()
function is called recursively for both the left and right subtrees. These calls occur for each node in the tree, of which there aren
nodes.
Combining the above two points, every time we create a node (which happens n
times), we may have to look through an entire list of size n
(in the worst case) to find the index of the root value. Thus, in the worst case, the time complexity of this algorithm becomes O(n^2)
, as the .index()
call dominates the complexity.
Space Complexity:
The space complexity of the function includes the following considerations:
-
The space required to store the created binary tree which will have
n
nodes. This takesO(n)
space. -
The recursive call stack, which would also go as deep as the height of the tree. In the worst case (a completely skewed tree), this would be
O(n)
. For a balanced tree, it would beO(log n)
. -
The additional space required for the slices of
inorder
andpostorder
arrays created for each recursive call. However, this does not use extra space in terms of additional elements as slices are usually implemented as views in Python. These slices do however keep a reference to the original array which could keep it from being garbage collected. The impact of this is less obvious and often considered asO(n)
in the context of the input size.
Adding it all up, the worst-case space complexity here is O(n)
due to the binary tree storage and the potential recursive call stack depth in a skewed tree.
Learn more about how to find time and space complexity quickly using problem constraints.
How does merge sort divide the problem into subproblems?
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
Want a Structured Path to Master System Design Too? Donāt Miss This!