0

I'm looking at LeetCode problem: 105. Construct Binary Tree from Preorder and Inorder Traversal:

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Template code:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:

I used the code that is provided in the Editorial of the challenge:

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:

        def array_to_tree(left, right):
            nonlocal preorder_index
            # if there are no elements to construct the tree
            if left > right: return None

            # select the preorder_index element as the root and increment it
            root_value = preorder[preorder_index]
            root = TreeNode(root_value)


            preorder_index += 1

            # build left and right subtree
            # excluding inorder_index_map[root_value] element because it's the root
            root.left = array_to_tree(left, inorder_index_map[root_value] - 1)
            root.right = array_to_tree(inorder_index_map[root_value] + 1, right)

            return root

        preorder_index = 0

        # build a hashmap to store value -> its index relations
        inorder_index_map = {}
        for index, value in enumerate(inorder):
            inorder_index_map[value] = index

        return array_to_tree(0, len(preorder) - 1)

Problem

My question is about running this test case:

preorder = [4,1,3,6,8]
inorder = [6,1,8,4,3]
tree = Solution().buildTree(preorder, inorder)

When running it, an exception occurs:

Traceback (most recent call last):
  File "main.py", line 43, in <module>
    tree = Solution().buildTree(preorder,inorder)
  File "main.py", line 30, in buildTree
    return array_to_tree(0, len(preorder) - 1)
  File "main.py", line 22, in array_to_tree
    root.left = array_to_tree(left, inorder_index_map[root_value] - 1)
  File "main.py", line 22, in array_to_tree
    root.left = array_to_tree(left, inorder_index_map[root_value] - 1)
  File "main.py", line 22, in array_to_tree
    root.left = array_to_tree(left, inorder_index_map[root_value] - 1)
  File "main.py", line 23, in array_to_tree
    root.right = array_to_tree(inorder_index_map[root_value] + 1, right)
  File "main.py", line 22, in array_to_tree
    root.left = array_to_tree(left, inorder_index_map[root_value] - 1)
  File "main.py", line 19, in array_to_tree
    root_value = preorder[preorder_index]
IndexError: list index out of range

Analysis

The following is my manual calculation:

The tree should look like this:

    4
   / \
  1   3
 / \
6   8

Hand Calculating:

preorder = [4, 1, 3, 6, 8]
hashmap: {6:0 ; 1:1 ; 8:2 ; 4:3 ; 3:4 }
preorderindex = 0

loop 1:

  left = 0 right = 3
  preorderindex = 0 => root value = 4 => new right = 2
  tree: 

    4

loop 2:

  left = 0 right = 2
  preorderindex = 1 => root value = 1 => new right = 0
  tree: 

      4
     /
    1

loop 3:

  left =0 right = 0
  preorderindex = 2 => root value = 3 => new right = 3
  tree:

       4
      /
     1
    /
   3

At this step, there is already an error, and I really wonder where is the mistake?

I'm so confused, I don't believe there is a mistake in this code, but then I can't figure out where is my mistake?

1 Answer 1

0

The preorder and inorder sequences that you have there are not compatible. There is no tree that has [4, 1, 3, 6, 8] as preorder and [6,1,8,4,3] as inorder sequences.

We can prove that as follows:

An inorder traversal will visit the "leftmost" node first, which in this case is node 6. The preorder sequence will only visit the leftmost node after having visited the nodes on the path from the root to that node, so that means the tree must have this branch:

         4
        /
       1
      /
     3
    /
   6

But that is a contradiction, that means in the inorder traversal, 6 and 3 should be visited before 1, but that is not the case.

Assuming you started out with a given tree:

    4
   / \
  1   3
 / \
6   8

...then indeed the inorder sequence is [6,1,8,4,3]. But the preorder sequence is not [4,1,3,6,8], but [4,1,6,8,3].

The sequence [4,1,3,6,8] is something different: it is a level-order (breadth-first) sequence.

As you provide inconsistent data to the solution code, it runs into an error.

Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.