Insertion in a binary search tree(data stored at leaf node only)

Question

I'm using Haskell for this class I'm in and I have to make an insertion of in a binary search tree with recursion. Here is my tree definition:

data Tree = Leaf Int | Branch Tree Tree

An example would be:

tree1 = Branch ((Branch (Leaf 2) (Leaf 4)) (Branch (Leaf 6) (Leaf 10)))

My insert function should get a Tree and an Int and return a Tree:

insert :: Tree -> Int -> Tree

I just cant understand how to go about this problem.

edit: I know pattern matching. Here is what i thought.

insert :: Tree -> Int -> Tree
insert (Leaf i) j = if (i > j) than Branch (Leaf j) (Leaf i)
                    else Leaf i
insert (Branch l r) j = Branch (insert l j) (insert r j)

I know this is wrong. It gets the value inserted more than once if there are two or more numbers greater than j.

edit2: So I followed @Willem Van Onsem suggestion and got this:

infimum :: Tree -> Int

infimum (Leaf i) = i;
infimum (Branch l r) = infimum r

insert :: Tree -> Int -> Tree
insert (Leaf i) j = if (j > i) then Branch (Leaf i) (Leaf j)
                    else Branch (Leaf j) (Leaf i)
insert (Branch l r) j = if (j > (infimum l)) then Branch l (insert r j)
                        else Branch (insert l j) r

It works. I guess it cant be done with one function only.

You haven't actually asked a question, which leads me to believe that the implicit question is "write my code for me." Please edit your question to show an attempt and/or a specific question. In the meantime, idownvotedbecau.se/noattempt — AJF
You can't build a binary search tree with that definition; it's just an inefficient encoding of a list, because there's no basis for deciding which branch to follow from any particular interior node. — chepner
A binary search tree is a tree that has the property that each node contains a unique value, and all values in the left (right) subtree of a given node X are smaller (greater) than the value at X. — chepner
@amalloy: you can move down the tree, for example taking the rightmost node of the left subtree to find the largest value of the right subtree, if the tree is balanced (we can balance the tree), then we can detect that in O(log n), based on that value, we search the left or right subtree, and each step we again perform the same action to detect the "spit value". — Willem Van Onsem

chepner chepner · Accepted Answer · 2019-05-18T19:29:04

Given your current type, you have no basis for deciding which subtree to insert the new value into; you don't have any values to compare to until you reach a leaf.

Start with a proper search tree:

data BST = Node Int BST BST | Empty

Each node contains a single value, and your insert function must maintain the search property, which states that for a given node Node x left right, all values in left are less than x, and all values in right are greater than x. (If you try to insert x when it is already present, you don't need to do anything: keys are unique.)

insert :: BST -> Int -> BST
insert Empty x = Node x Empty Empty  -- replace the empty tree with a single leaf
insert t@(Node y left right) | x == y = t  -- do nothing
                             | x < y = ...
                             | otherwise = ...

I leave it as an exercise to determine what to do in the cases where x /= y.

Insertion in a binary search tree(data stored at leaf node only)

2 Answers