🤖
Data Structures and Algorithms
  • CS Theory And Problems
  • Big O
    • Big O Notation
  • Algorithms
    • Binary Search
    • Breadth First Search (BFS)
    • Depth First Search (DFS)
    • Dynamic Programming
    • Kadane's Algorithm
    • Kahn's Algorithm
    • Quickselect
    • Recursion
    • Sorting Algorithms
    • Sliding Window
  • Data Structures
    • Binary Heap
    • Graph
    • Linked List
    • Trees
  • Problems
    • LeetCode
      • 1. Two Sum
      • 3. Longest Substring Without Repeating Characters
      • 5. Longest Palindromic Substring
      • 11. Container With Most Water
      • 15. 3 Sum
      • 19. Remove Nth Node From End of List
      • 20. Valid Parentheses
      • 33. Search in Rotated Sorted Array
      • 49. Group Anagrams
      • 53. Maximum Subarray
      • 55. Jump Game
      • 56. Merge Intervals
      • 76. Minimum Window Substring
      • 98. Validate Binary Search Tree
      • 105. Construct Binary Tree from Preorder and Inorder Traversal
      • 121. Best Time to Buy and Sell Stock
      • 133. Clone Graph
      • 141. Linked List Cycle
      • 152. Maximum Product Subarray
      • 153. Find Minimum in Rotated Sorted Array
      • 200. Number of Islands
      • 206. Reverse Linked List
      • 207. Course Schedule
      • 217. Contains Duplicate
      • 226. Invert Binary Tree
      • 238. Product of Array Except Self
      • 242. Valid Anagram
      • 297. Serialize and Deserialize Binary Tree
      • 347. Top K Frequent Elements
      • 417. Pacific Atlantic Water Flow
      • 424. Longest Repeating Character Replacement
      • 435. Non-overlapping Intervals
      • 647. Palindromic Substrings
Powered by GitBook
On this page
  • Description
  • Solution
  • Observations
  • Example walk through
  • Code
  1. Problems
  2. LeetCode

105. Construct Binary Tree from Preorder and Inorder Traversal

Previous98. Validate Binary Search TreeNext121. Best Time to Buy and Sell Stock

Last updated 3 years ago

Description

See:

We are given two arrays as inputs, one containing the traversal of a tree and one containing the traversal of the same tree. Our task is to recreate the tree structure given those inputs.

Solution

The problem gives as an example:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

The expected tree structure is:

Expected tree structure from the given input. Image from leetcode

Observations

  • Preorder traversal processes the tree in order: Node -> Left -> Right

  • Inorder traversal processes the tree in order: Left -> Node -> Right

  • From these two facts come the following observations:

    • The first element in the preorder array will always be the root node of the tree.

    • In the inorder array, elements to the left of the node will form the left side of the tree. Elements to the right of the node will form the right side of the tree.

    • In this case we want to create subtrees in order to build the entire tree.

    • Imagining the function already exists, I would want to do something like

node.left = make_tree()
node.right = make_tree()
  • The first two facts and observations are true for the subtrees, but with subportions of the preorder and inorder arrays.

Example walk through

From the preorder array [3,9,20,15,7], the root node is the first element, which is 3.

In the inorder array [9,3,15,20,7], items to the left of 3 are the left subtree. Items to the right of 3 are the right subtree. So, 9 is the left side subtree. 15, 20 and 7 form the right side subtree.

We can think of the tree structure as the following diagram.

We know 3 is the root, we need to form the left and right subtrees to complete the tree. We know there will be something on the left and something on the right, but we do not know its structure yet. We will break the creation of the left and right subtrees into subproblems.

To form the left subtree, we get the next element from the preorder array which is 9. This is the root node for the left subtree. We will only use a portion of the inorder array, since we only want those elements that are children of node 9. Looking at the inorder array, [9,3,15,20,7], there are no elements to the left of 9. So, it has no left children. The items to the right of 9 are not part of its children because 3 is the root. So, 9 has no right children. We can think of the tree structure now as:

We now get the next element of the preorder array, [3,9,20,15,7], which is 20. 20 is the root of the right side subtree. Again, we will only use a portion of the inorder array, since we only want those elements that are children of node 20. Looking at the inorder array, [9,3,15,20,7], there is one element to the left of 20 which has not been used, 15. It is the root node of that left subtree. There is one element to the left of 20, 7. It is the root of that right subtree. We can think of the tree structure now as:

We now get the next element of the preorder array, [3,9,20,15,7], which is 15. 15 is the root of the left side subtree. Again, we will only use a portion of the inorder array, since we only want those elements that are children of node 15. Looking at the inorder array, [9,3,15,20,7], there are no elements to the left of 15 which have not been used. There are also no elements to the right of 15 that have not been used. So, 15 has no children. We can think of the tree structure now as:

We now get the next element of the preorder array, [3,9,20,15,7], which is 7. 7 is the root of the right side subtree. Again, we will only use a portion of the inorder array, since we only want those elements that are children of node 7. Looking at the inorder array, [9,3,15,20,7], there are no elements to the left of 7 which have not been used. There are also no elements to the right of 7 as we've reached the end of the array. So, 7 has no children. The tree has now been formed:

Code

From the above walk through we will need to keep track of the following:

  • the index of the elements in the inorder array

    • We will need to look up the position of the root node in the inorder array. Indexes less than the node index will be left children. Indexes that are greater than the node index will be right children. We can store each element's index in a dict to make look up easy.

  • the current range of indexes to use in the inorder array

    • we can keep track of the start and end indexes to use in the inorder array.

    • For the left side, the indexes to use will be from the start -> node index - 1

    • For the right side, the indexes to use will be from node index + 1 -> end

    • For the root node, the entire inorder array will be used. So, the start will be 0 and end will be len(inorder) - 1 (4 in this example)

      • In this example, when the root node passes in the bounds for the left and right subtrees the indexes will be:

        • left: start: 0 end: 0

        • right: start: 2 end: 4

  • the current element in the preorder array

    • Keep track of this at the class level, as we do not want to recursively get the preorder array elements. We just want to iterate through them.

class Solution:

    def __init__(self):
        # The index of the preorder array element currently being processed
        self.preorder_index = 0

    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        def make_tree(start, end):
            """
            :param start: the index to start at in the inorder array
            :param end: the index to end at in the inorder array
            :return: the TreeNode structure or None if the end index is less than the start index
            """
            if end < start:
                return None
            root = TreeNode(preorder[self.preorder_index])
            self.preorder_index += 1
            root_index = location[root.val]
            root.left = make_tree(start, root_index - 1)
            root.right = make_tree(root_index + 1, end)
            return root

        # set self.preorder_index to 0 in case the buildTree method is called multiple times on the Solution instance.
        # If it wasn't set then the self.preorder_index would be a value used in the previous invocation.
        self.preorder_index = 0
        location = {}
        for index, value in enumerate(inorder):
            location[value] = index
        return make_tree(0, len(inorder) - 1)

Time complexity: O(N)

Space complexity: O(N)

Trees and traversal use recursion for an elegant solution. Using the we can break the problem into subproblems.

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
preorder
inorder
top-down recursive strategy
3 is the root. 9 will form the left side of the tree. 15, 20 and 7 will form the right side of the tree
Left subtree is formed
Starting to form right subtree. We know 20 is the root node for the left and right subtrees
The left subtree at 15 has been formed
Tree has been formed by breaking it into subproblems