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:

1. Identify the root node as the last element in the postorder list.
2. Find the position of this root in the inorder list to partition it into the left and right subtree nodes.
3. Recursively build the left subtree using the left partition of inorder and postorder lists.
4. 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.
5. 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.

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:

1    3
2   / \
3  9  20
4    /  \
5   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 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:

1. 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.

2. 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:

1    3
2   / \
3  9  20
4    /  \
5   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

Time and Space Complexity

Time Complexity:

The time complexity of the provided function can be analyzed based on the operations it performs:

1. 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.

2. 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:

1. The space required to store the created binary tree which will have n nodes. This takes O(n) space.

2. 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).

3. 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.