Rebuild a binary tree from preorder and inorder lists

Question

Hi I'm trying to rebuild a binary tree, I almost got it, except it throws me an error and I don't know why

buildTree :: (Ord a, Eq a) => [a] -> [a] -> Tree a
buildTree [] [] = Empty
buildTree preOrd inOrd = Node root left right 
where root  = head preOrd
      left = buildTree leftPreOrd leftInOrd
      right = buildTree rigthPreOrd leftInOrd

      Just rootInd = elemIndex root inOrd
      leftPreOrd   = tail (take (rootInd + 1) preOrd)
      rigthPreOrd  = tail (drop rootInd preOrd)

      leftInOrd    = take rootInd inOrd
      rightInord   = drop (rootInd + 1) inOrd

When I call it using

buildTree [10,5,2,6,14,12,15] [2,5,6,10,12,14,15]

it throws me this:

Exception: reconstruir.hs:26:11-45: Irrefutable pattern failed for pattern Just rootInd

Answer 1

The runtime is failing on this line:

Just rootInd = elemIndex root inOrd

elemIndex is returning Nothing when running your example input, but your code says it will always return a Just, so the runtime crashes. You need to handle the case where elemIndex root inOrd returns Nothing.

Perhaps more importantly, you should enable all warnings with the -Wall flag to show up as compiler errors so that your code wouldn't compile to begin with.

Answer 2

@chepner has spotted the error. If you'd like to know how to find and fix these sorts of errors yourself in the future, you may find the following answer helpful...

First, it helps to find the smallest test case possible. With a few tries, it's not hard to get your program to fail on a 2-node tree:

> buildTree [5,2] [2,5]
Node 5 (Node 2 Empty Empty) (Node *** Exception: Prelude.head: empty list

Now, try tracing the evaluation of buildTree [5,2] [2,5] by hand. If you evaluate this first buildTree call manually, you'll find the variables involved have values:

preOrd = [5,2]
inOrd = [2,5]
Just rootInd = Just 1

leftPreord = tail (take 2 [5,2]) = [2]
rightPreord = tail (drop 1 [5,2]) = []

leftInOrd = take 1 [2,5] = [2]
rigthInord = drop 2 [2,5] = []

root = 5
left = buildTree [2] [2]
right = buildTree [] [2]

Everything looks fine, except right, which tries to build a tree with incompatible preorder and inorder lists. That's what causes the error, since buildTree [] [2] tries to take the head of an empty list. (The error message is a little different for your test case, but the underlying cause is the same.)

This pinpoints the problem as the second argument to buildTree in the definition of right -- the value 2 shouldn't be included in the (empty) right tree. From there, it's easy to spot and fix the typo in the definition of right so it reads:

read = buildTree rigthPreOrd rightInOrd

After that fix, things seem to work okay.