Building a Tree in Haskell

Question

I am new to Haskell and I am trying to build a tree which holds integers and every element in the left subtree is <= node value. This is the code that I have written so far but I don't know how to do the recursion inside. I would appreciate it if you could give me some guidance.

data Tree = Leaf | Node Int Tree Tree
    deriving (Eq, Show, Read, Ord)

insert :: Int -> Tree -> Tree
insert x (Tree n i t1 t2) = 

From what I understand is that I have to check each node of tree and see if there is an int to it and then recursively search the subtrees. Please help

thanks

EDIT:

I managed to do something but it seems that the new nodes fail to be created or I am checking it wrong, this is the new code:

data Tree = Leaf | Node Int Tree Tree
    deriving (Eq, Show, Read, Ord)

insert :: Int -> Tree -> Tree
insert x Leaf = Node x Leaf Leaf
insert x (Node i t1 t2)  
              | x <= i    = insert x t1
              | otherwise = insert x t2

To check it I write:

let tree = insert 5 (insert 10 ( insert 11 ( insert 12 (insert 15 tree))))

But when I write in the ghci:

tree

I get:

Node 5 Leaf Leaf

Answer 1

The problem with your recursive case for Node is that although you call insert to make a new sub tree on either the left or the right, you don't rebuild the parent tree afterwards, you just return the new sub tree.

For example the first case should be Node i (insert x t1) t2, and similarly for the second case.

Answer 2

When you are inserting into a node, you are returning what would be inserted into one side of the Node, not a new Node with the data inserted into one side of it. Only at the Leaf level are you making a new node.

insert :: Int -> Tree -> Tree
insert x Leaf = Node x Leaf Leaf
insert x (Node i t1 t2)  
          | x <= i    = Node i (insert x t1)  t2
          | otherwise = Node i  t1           (insert x t2)