Adding a leaf to Binary Search Tree, Haskell -

the type defined

data bst = makenode bst string bst           | empty 

i'm trying add new leaf tree, don't understand how recursion.

the function set this

add :: string -> bst -> bst 

the advantage of using binary trees need @ "current part" of tree know insert node.

so, let's define add function:

add :: string -> bst -> bst 

if insert empty tree (case #1), create leaf directly:

add s empty = makenode empty s empty 

if want insert node (case #2), have decide sub-node insert value in. use comparisons test:

add s t@(makenode l p r) -- left, pivot, right   | s > p     = node l p (add s r) -- insert right subtree   | s < p     = node (add s l) p r -- insert left subtree   | otherwise = t -- tree contains value, return 

note not rebalance binary tree. binary tree rebalancing algorithms can complicated , require lot of code. so, if insert sorted list binary tree (e.g. ["a", "b", "c", "d"]), become unbalanced, such cases uncommon in practice.