Haskell: binary search tree with a list

Question

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

Answer 1

Your insert function is fine, but treeListInsert is equivalent to foldr treeInsert Nil. The base case is the end of the list, not the beginning. The tree you get looks wrong (4 has 6 as a left child), but that's because you drew it wrong, not because Haskell gave you a bad result.