How can I create an indexed binary tree from a sorted list in Haskell?

user_12868928 0
Viewed 321

I am trying to make a tree out of a sorted list so that I can search it later.

The problem is

I have to return the index of the number if it is found else I return -1, so I created this function.

data Tree e i = Leaf e i | Node (Tree e i) e i (Tree e i)
    

occurs :: Int -> Tree Int Int -> Int 
occurs x (Leaf y i)     | x == y    = i 
                        | otherwise = -1
occurs x (Node l y i r) | x == y    = i 
                        | x < y     = occurs x l 
                        | otherwise = occurs x r

My input is comming in the format (as a string)

3       # The length of as
1 5 7   # as
2       # The length of bs
5 6     # bs

where I receive 2 lists as and bs as is gonna be the Tree and bs is the numbers I want to check if they exist in the tree (and where)

And the expected output is:

1
-1

where 5 is found on index 1 and 6 is not found so I return -1

So I am parsing the input:

parse :: [Int] -> ([Int], [Int])
parse (n: xs) = (take n xs, tail $ drop n xs) 

solve :: [Int] -> [Int]
solve xs = func as bs
    where (as, bs) = parse xs

main ::IO ()
main = interact $ unlines . map show . solve . map read . words

And then I need to call a function func which will create my tree from the list as and then use the occurs function to search the tree for each element in bs

So my question is

  • How can I make the tree so that it contains the indexes, from the lists?
  • And is my type created in the right way for this problem?

My Haskell level = reached the Types and classes chapter, in the Cambridge Haskell book by GH, and following the HaskellRank series on youtube.

binary-tree data-structures algorithm haskell
1 Answers

You can construct a Binary Search Tree using a divide and conquer approach and keep a similar version of yours 'occurs' method:

  1. Take the element at center of the ordered list as root. If there are ties (the list has even length) choose any you like. It doesn't matter.
  2. Recursively solve the problem with all elements to the left of the selected index and add the returned tree as left child of current root. If there are no elements to the left then add a null reference on the left child.
  3. Recursively solve the problem with all elements to the right of the selected index and add the returned tree as right child of current root. If there are no elements to the right then add a null reference on the right child.

This divide and conquer approach guarantees a O(log n) height of the tree where n is length of the ordered list. The construction of the tree is O(n) and is a correct binary search tree because as the list is ordered we know that all elements on the left side are lower or equal than the current one and all elements on the right side are greater or equal than the current one.

The type creation is flaw as your construction of a tree rely on leaf nodes and nodes that have not null left and right child which is not true in almost any input. You can try to construct a tree with 2 nodes to see what i mean. Other not so Haskell design is the use of -1 as no existence of solution since Haskell has an integrated type of Maybe created for these cases but if you need to do that it's at the end your choice.

user_137431050
Related