106. Construct Binary Tree from Inorder and Postorder Traversal

MediumTreeArrayHash TableDivide and ConquerBinary Tree

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 and postorder, 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 hence None is returned.
If the postorder list is not empty, the last element of postorder is the root of the tree or subtree that we are currently building. This value is extracted and used to create a new TreeNode.
The position of the root element in the inorder array is found using the index method. This index is crucial as it helps to divide the inorder list into left and right subtrees for the current root.
Using the index i found, the inorder 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 the buildTree 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 Evaluator

Example 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:

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 value 9.

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 index 3 (considering 0 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] (before 20 in postorder list)
- Postorder right subtree: [7] (before 20 in postorder list)

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.
Subtree with 7 as root:
- Similarly, as 7 is alone in its postorder and inorder lists, it also has no children.

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:

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 the inorder list takes O(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 are n 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 takes O(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 be O(log n).
The additional space required for the slices of inorder and postorder 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 as O(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.

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

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructure

Overlapping subproblems

Non-overlapping subproblems

Constant time subproblems