I am trying to build a binary search tree, but it doesn't work as expected. For example, treeListInsert [7,12,6,4,8] gives me Node 8 (Node 4 Nil (Node 6 Nil (Node 7 Nil Nil))) (Node 12 Nil Nil), which is wrong. Is there anything I did wrong? Thanks.
-- the tree structure should be
-- 7
-- / \
-- 6 12
-- / /
-- 4 8
-- but results
-- 8
-- / \
-- 4 12
-- / \
-- 6 7
-- define the data structure
-- deriving Show to show Node in GHCI
data Tree a = Nil | Node a (Tree a) (Tree a) deriving Show
-- | treeInsert takes any number and
-- and return a Node
treeInsert :: Ord a => a -> Tree a -> Tree a
treeInsert x Nil = Node x Nil Nil -- build a Node
treeInsert x (Node root left right)
| x == root = Node root left right -- avoid duplicate
| x < root = Node root (treeInsert x left) right -- insert a node on a left
| x > root = Node root left (treeInsert x right) -- insert a node on the right
-- | treeListInsert takes a list of numbers
-- and return a tree using treeInsert function
treeListInsert :: (Ord a) => [a] -> Tree a
treeListInsert [] = Nil -- empty list return Nil
treeListInsert (x:xs) = treeInsert x (treeListInsert xs) -- iterate through the list and insert x to tree repeatedly
