-- BINARY SEARCH TREE (BinaryTree)
-- LEFT FROM = -> type constructor -> cant be created as value
-- RIGHT FROM = -> value constructor -> can be created as value
-- -> There will never be BinaryTree 1 as value. Since BinaryTree 1 is either EmptyTree or
-- Node 1 (EmptyTree | Node val (EmptyTree | Node val ....))
data BinaryTree a
  = EmptyTree
  | Node a (BinaryTree a) (BinaryTree a)
  deriving (Show, Read, Eq)

-- helper function that determines whether the tree is empty.
isEmptyTree :: BinaryTree a -> Bool
isEmptyTree EmptyTree = True
isEmptyTree _ = False

-- helper function that creates a base tree(node empty empty) for given number.
createBaseTree :: a -> BinaryTree a
createBaseTree x = Node x EmptyTree EmptyTree

-- three cases: eq -> drop, bigger -> right, smaller -> left
-- Notation: first BinaryTree(a) is the left leaf and second BinaryTree(a) is the right leaf.
insertInBinaryTree :: (Ord a) => BinaryTree a -> a -> BinaryTree a
insertInBinaryTree EmptyTree input = Node input EmptyTree EmptyTree
insertInBinaryTree (Node x leftTree rightTree) input
  | input == x = Node x leftTree rightTree
  | input < x =
    if isEmptyTree leftTree
      then Node x (createBaseTree input) rightTree
      else Node x (insertInBinaryTree leftTree input) rightTree
  | input > x =
    if isEmptyTree rightTree
      then Node x leftTree (createBaseTree input)
      else Node x leftTree (insertInBinaryTree rightTree input)

-- generate some numbers to insert into tree
genNumbers = map (\x -> if even x then x + 10 else x) [1 .. 5]

-- test implementation by inserting numbers into BinaryTree with base 10
insertNumbersIntoTree =
  foldl (\acc x -> insertInBinaryTree acc x) (createBaseTree 10) genNumbers