# Untitled

a guest
Oct 15th, 2021
194
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. -- BINARY SEARCH TREE (BinaryTree)
2. -- LEFT FROM = -> type constructor -> cant be created as value
3. -- RIGHT FROM = -> value constructor -> can be created as value
4. -- -> There will never be BinaryTree 1 as value. Since BinaryTree 1 is either EmptyTree or
5. -- Node 1 (EmptyTree | Node val (EmptyTree | Node val ....))
6. data BinaryTree a
7.   = EmptyTree
8.   | Node a (BinaryTree a) (BinaryTree a)
10.
11. -- helper function that determines whether the tree is empty.
12. isEmptyTree :: BinaryTree a -> Bool
13. isEmptyTree EmptyTree = True
14. isEmptyTree _ = False
15.
16. -- helper function that creates a base tree(node empty empty) for given number.
17. createBaseTree :: a -> BinaryTree a
18. createBaseTree x = Node x EmptyTree EmptyTree
19.
20. -- three cases: eq -> drop, bigger -> right, smaller -> left
21. -- Notation: first BinaryTree(a) is the left leaf and second BinaryTree(a) is the right leaf.
22. insertInBinaryTree :: (Ord a) => BinaryTree a -> a -> BinaryTree a
23. insertInBinaryTree EmptyTree input = Node input EmptyTree EmptyTree
24. insertInBinaryTree (Node x leftTree rightTree) input
25.   | input == x = Node x leftTree rightTree
26.   | input < x =
27.     if isEmptyTree leftTree
28.       then Node x (createBaseTree input) rightTree
29.       else Node x (insertInBinaryTree leftTree input) rightTree
30.   | input > x =
31.     if isEmptyTree rightTree
32.       then Node x leftTree (createBaseTree input)
33.       else Node x leftTree (insertInBinaryTree rightTree input)
34.
35. -- generate some numbers to insert into tree
36. genNumbers = map (\x -> if even x then x + 10 else x) [1 .. 5]
37.
38. -- test implementation by inserting numbers into BinaryTree with base 10
39. insertNumbersIntoTree =
40.   foldl (\acc x -> insertInBinaryTree acc x) (createBaseTree 10) genNumbers
41.
RAW Paste Data