CODEWITHSUNDEEP
haskellbinary-search-treesearch-tree
Mr. Moose
Mr. Moose

Reputation: 111

Binary Search Tree in Haskell

I am starting to learn Haskell and therefore I tried to implement a Binary Search Tree. My current code looks like this:

data SearchTree = Empty | Node Int SearchTree SearchTree
  deriving Show


insert :: SearchTree -> Int -> SearchTree
insert Empty x = (Node x Empty Empty)
insert (Node n tl tr) x = if (x > n)
                       then insert tr x
                       else insert tl x

But somehow the second part of the insert function is not working correctly. If I try these lines of code:

insert (Node 2 Empty Empty) 4

the result is Node 4 Empty Empty instead of a result like: Node 2 Empty (Node 4 Empty Empty) that I expected.

Can someone tell me, what I did wrong? Thanks :)

Upvotes: 0

Views: 338

Answers (1)

Aplet123
Aplet123

Reputation: 35482

When you recurse, you lose the information on the outer node. You have to re-wrap the result in a Node:

data SearchTree = Empty | Node Int SearchTree SearchTree
  deriving Show


insert :: SearchTree -> Int -> SearchTree
insert Empty x = (Node x Empty Empty)
insert (Node n tl tr) x = if (x > n)
                       -- note the Node n tl (new_branch)
                       then Node n tl (insert tr x)
                       else Node n (insert tl x) tr

Upvotes: 3

Related Questions