samuel zihIn this blog post, we’ll walk through a solution to the well-known problem: constructing a binary tree from its preorder and inorder traversal arrays. We'll not only explain the logic behind the algorithm but also show how the recursive process works step-by-step. Along the way, we’ll delve into the concepts that govern the solution and break it down for easy understanding.
Problem Statement
You are given two arrays representing the preorder and inorder traversal of a binary tree. Your task is to construct the binary tree from these arrays.
Preorder traversal: Visit the root node first, then recursively visit the left subtree, followed by the right subtree.
(Root → Left → Right)
Inorder traversal: Recursively visit the left subtree first, then visit the root, and finally, visit the right subtree.
(Left → Root → Right)
example:
Key Concepts
To understand how to solve this problem, we need to grasp the structure of binary trees and how their preorder and inorder traversals work:
Preorder Traversal gives us the root of the tree first.
Inorder Traversal provides us the relative positioning of the left and right subtrees concerning the root.
From this, we can break down the problem recursively:
The first element of the preorder array is the root of the tree.
The inorder array splits into two parts: the left part consists of elements belonging to the left subtree, and the right part consists of elements in the right subtree.
Using the root node, we can recursively build the left and right subtrees.
The Recursive DFS Algorithm
Let’s break down the recursive process. We’ll use the following recursive function to build the tree:
Walkthrough: Constructing the Left Subtree
Let's start by building the leftmost branch of the tree for the example preorder and inorder arrays.
Initial Call:
Preorder: [10, 6, 4, 2, 8, 14, 12, 13, 16]
Inorder: [2, 4, 6, 8, 10, 12, 13, 14, 16]
From the preorder array, the first element is 10, which is the root of the tree. The inorder array splits around 10:
Left subtree: [2, 4, 6, 8]
Right subtree: [12, 13, 14, 16]
First Recursive Call (Left Subtree of 10):
Preorder: [6, 4, 2, 8]
Inorder: [2, 4, 6, 8]
Here, 6 is the next root (first element of the preorder), and the inorder array splits into:
Left subtree: [2, 4]
Right subtree: [8]
Second Recursive Call (Left Subtree of 6):
Preorder: [4, 2]
Inorder: [2, 4]
Now, 4 becomes the next root, and the inorder array splits again:
Left subtree: [2]
Right subtree:
Third Recursive Call (Left Subtree of 4):
Preorder: [2]
Inorder: [2]
Finally, 2 is the root of this subtree, and since there are no more elements in the preorder or inorder arrays, we reach the base case and return None for both the left and right children of 2.
Walkthrough: Constructing the Right Subtree
Now, let's switch to building the rightmost branch, which starts from the root's right subtree.
Preorder: [10, 6, 4, 2, 8, 14, 12, 13, 16]
Inorder: [2, 4, 6, 8, 10, 12, 13, 14, 16]
Initial Call (Right Subtree of 10):
Preorder: [14, 12, 13, 16]
Inorder: [12, 13, 14, 16]
The next root is 14, and the inorder array splits around 14:
Left subtree: [12, 13]
Right subtree: [16]
First Recursive Call (Left Subtree of 14):
Preorder: [12, 13]
Inorder: [12, 13]
Here, 12 is the next root, and the inorder array splits into:
Left subtree: []
Right subtree: [13]
Second Recursive Call (Right Subtree of 12):
Preorder: [13]
Inorder: [13]
Finally, 13 is the root of this subtree, and since there are no more elements in the preorder or inorder arrays, we reach the base case and return None for both the left and right children of 13.
At this point, we’ve completed the rightmost branch of the tree:
Completing the Tree
Now, we can merge the left and right branches to form the full tree:
Code Explanation
Let’s go over the code section by section:
1. Base Case:
This checks whether either the preorder or inorder arrays are empty. If so, we’ve reached a leaf node and return None.
2. Root Node Construction:
The first element of the preorder array is always the root of the current subtree. We create a new TreeNode with this value.
3. Find Root Index in Inorder Array:
To split the left and right subtrees, we need to find where the root value appears in the inorder array. The elements to the left of this index form the left subtree, and the elements to the right form the right subtree.
- Recursively Build Left and Right Subtrees:
Abstract Reasoning for root.left:
root.left =
self.buildTree(
preorder so : rootval on left and we take the right element after the rootval to the inorderindex of the rootval;,
inorder so : root_val is on the right and we take element from the start of the inorder array up until the inorderindex of rootval)
Explanation:
In the preorder traversal, the first element is always the root. After that, the elements belonging to the left subtree will come before those of the right subtree.
The code preorder[1:root_index_in_inorder+1] is extracting the portion of the preorder array that corresponds to the left subtree.
This range is from the second element (right after the root) up to the position determined by root_index_in_inorder + 1.
This index is the length of the left subtree as indicated by the inorder traversal.
In the inorder traversal, elements to the left of root_index_in_inorder are part of the left subtree.
inorder[:root_index_in_inorder] correctly captures all elements from the start of the inorder array up until the root value, indicating the left subtree.
Abstract Reasoning for root.right:
root.right =
self.buildTree(
preorder so : rootval on left and we take the right element after the rootval to the inorderindex of the rootval;,
inorder so : root_val is on the left and we take element from inorderindex of rootval in inorder till the end of the array)
Explanation:
In the preorder traversal, after the left subtree has been accounted for, the remaining elements belong to the right subtree.
The code preorder[root_index_in_inorder+1:] captures the elements of the preorder array that belong to the right subtree.
This starts after the left subtree and extends to the rest of the array.
In the inorder traversal, elements to the right of root_index_in_inorder belong to the right subtree.
inorder[root_index_in_inorder+1:] correctly slices the inorder array starting from just after the root and extending to the end, representing the right subtree.
Conclusion
Constructing a binary tree from preorder and inorder arrays is a classic recursive problem. By understanding how these two traversals work and breaking the problem down recursively, we can effectively rebuild the entire tree. I hope this walkthrough clarified the recursive process, and the detailed breakdown of both the leftmost and rightmost branches gives you a better understanding of how the algorithm works in practice.
Feel free to experiment with other examples to deepen your understanding of this elegant solution!
