Build Binary Tree from Preorder and Inorder Traversal
Statement
Create a binary tree from two integer arrays preorder and inorder, where preorder represents a preorder traversal of a binary tree, and inorder represents an inorder traversal of the same tree.
Constraints
- 1 ≤
preorder.length(),inorder.length()≤ 1000 preorder.length()=inorder.length()- -1000 ≤
preorder[i],inorder[i]≤ 1000
Solution
"""
production algorithm
"""
from data_structures.binary_tree.binary_tree import BinaryTreeNode
class Solution:
def build_tree(self, preorder, inorder):
"""
time complexity O(n)
space complexity O(n)
"""
preorder = preorder[::-1]
indexer = {inorder[index]: index for index in range(len(inorder))}
low, high = 0, len(preorder) - 1
return self.build_tree_helper(preorder, indexer, low, high)
def build_tree_helper(self, preorder, indexer, low, high):
"""
time complexity O(n)
space complexity O(n)
"""
if high < low:
return None
data = preorder.pop()
mid = indexer[data]
root = BinaryTreeNode(data)
root.left = self.build_tree_helper(preorder, indexer, low, mid - 1)
root.right = self.build_tree_helper(preorder, indexer, mid + 1, high)
return root"""
unit tests
"""
from unittest import TestCase
from algorithms.dfs.build_binary_tree_from_preorder_and_inorder_traversal.solution import Solution
class SolutionTestCase(TestCase):
def test_balanced_tree(self):
# Given
preorder = [-1, -7, -9, -18, -8, -4, -6, -3, 10, 6, 3, 9, 16, 11, 18]
inorder = [-18, -9, -8, -7, -6, -4, -3, -1, 3, 6, 9, 10, 11, 16, 18]
solution = Solution()
# When
root = solution.build_tree(preorder, inorder)
actual = str(root)
# Then
expected = str(preorder)
self.assertEqual(actual, expected)
def test_left_skewed_tree(self):
# Given
preorder = [10, -4, -8, -9, -18, -6, -7, 3, -1, -3, 9, 6, 16, 11, 18]
inorder = [-18, -9, -8, -7, -6, -4, -3, -1, 3, 6, 9, 10, 11, 16, 18]
solution = Solution()
# When
root = solution.build_tree(preorder, inorder)
actual = str(root)
# Then
expected = str(preorder)
self.assertEqual(actual, expected)
def test_degenerate_tree(self):
# Given
preorder = [-18, -9, -8, -7, -6, -4, -3, -1, 3, 6, 9, 10, 11, 16, 18]
inorder = [-18, -9, -8, -7, -6, -4, -3, -1, 3, 6, 9, 10, 11, 16, 18]
solution = Solution()
# When
root = solution.build_tree(preorder, inorder)
actual = str(root)
# Then
expected = str(preorder)
self.assertEqual(actual, expected)Strategy
Depth First Search.
Explanation
The algorithm uses a preorder traversal with recursion. Before traversal , the preorder integer array is reversed, and a reverse index is created of the inorder integer array. The reversed array and reverse index are used to minimize the time complexity to access elements from linear to constant time. Low and high pointers are also used to know the elements in the left and right subtrees of a node. Next, traversal gets underway.
For each step of recursion, the next element of preorder traversal is popped from the end of the reversed array in constant time. Then, the index of the current element in the inorder array is looked up in the reverse index in constant time. The low and high pointers are used as lower and upper bounds of the inorder array.
All elements at indexes greater than or equal to the lower bound and less than the index of the current element are in the left subtree of the current element. Likewise all elements at indexes less than or equal to the upper bound and greater than the index of the current element are in the right subtree of the current element. As long as a left subarray is nonempty, another left subtree exists. Likewise as long as a right subarray is nonempty, another right subtree exists.
Time Complexity
The algorithm visits every element of the binary tree once. Therefore, the time complexity of the algorithm is O(n).
Space Complexity
In the case of a degenerate tree, the depth of recursion is proportional to n, where n is the number of elements. Therefore, the auxiliary space complexity of the algorithm is O(n).
