Adding a leaf to Binary Search Tree, Haskell

Question

The type is defined as

data BST = MakeNode BST String BST
          | Empty

I'm trying to add a new leaf to the tree, but I don't really understand how to do it with recursion.

the function is set up like this

add :: String -> BST -> BST

Your definition of BST won't work. I think you mean data BST = MakeNode String BST BST | Empty, right? — dflemstr
– dflemstr, Commented Mar 8, 2012 at 17:32

dflemstr · Accepted Answer · 2012-03-08 18:00:40Z

2

The advantage of using binary trees is that you only need to look at the "current part" of the tree to know where to insert the node.

So, let's define the add function:

add :: String -> BST -> BST

If you insert something into an empty tree (Case #1), you just create a leaf directly:

add s Empty = MakeNode Empty s Empty

If you want to insert something into a node (Case #2), you have to decide which sub-node to insert the value in. You use comparisons to do this test:

add s t@(MakeNode l p r) -- left, pivot, right
  | s > p     = Node l p (add s r) -- Insert into right subtree
  | s < p     = Node (add s l) p r -- Insert into left subtree
  | otherwise = t -- The tree already contains the value, so just return it

Note that this will not rebalance the binary tree. Binary tree rebalancing algorithms can be very complicated and will require a lot of code. So, if you insert a sorted list into the binary tree (e.g. ["a", "b", "c", "d"]), it will become very unbalanced, but such cases are very uncommon in practice.

edited Mar 8, 2012 at 18:00

answered Mar 8, 2012 at 17:42

dflemstr

26.3k5 gold badges75 silver badges107 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

user1204349 Over a year ago

@dflemstr could you explain the @ symbol quickly?

dflemstr Over a year ago

The @ symbol creates a name for the whole pattern to the right of it. So, if I do t @ (MakeNode l p r), it's like saying let t = MakeNode l p r in in the code that follows, except that the program won't create a new MakeNode; it will just reuse the old one.

user1204349 Over a year ago

okay, so its makes it so you can either use the the whole BST by using t, and use the pattern by using (MakeNode l p r), basically?

dflemstr Over a year ago

Yes, you could describe it like that.

user1204349 Over a year ago

okay, thanks alot. I was trying to do something like that yesterday I a didn't know how.

Collectives™ on Stack Overflow

Adding a leaf to Binary Search Tree, Haskell

1 Answer 1

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related