How can we insert an element in a BST in Haskell

Overview

Haskell is a functional programming language. It is a type of programming paradigm where the focus is on changing data through expressions that don’t have side effects. These expressions are often called pure functions. Let’s see how we can implement a pure function, which inserts an element in a binary search tree (BST).

Recursive solution

The most intuitive way to insert an element in a BST is by using recursion. We use the following algorithm for recursion:

  • If the tree is empty, then we insert the root node.
  • If the inserted key is less than the root key, then we recurse at the left subtree. Otherwise, we recurse at the right subtree. When the tree ends, the function inserts at the left (if the inserted key is less than the current key), and vice versa.
data Tree a = Nil | Node (Tree a) (Tree a) a
indentation:: Int-> String
indentation = \indents ->
    case indents of
        0 -> ""
        1 -> "+---" 
        _ -> "|   " ++ indentation (indents-1) 
printTree:: Show a => Tree a -> Int -> String
printTree = \tree -> \level ->
    case tree of
        Nil -> ""
        Node Nil Nil b -> (show b)
        Node left Nil b -> (show b) ++ "\n" ++ indentation (level) ++ (printTree left (level+1))
        Node Nil right b -> (show b) ++ "\n" ++ indentation (level) ++ (printTree right (level+1))
        Node left right b -> (show b) ++ "\n" ++ indentation (level) ++ (printTree left (level+1)) ++ "\n" ++ indentation (level) ++ (printTree right (level+1))
instance Show a => Show (Tree a) where
    show = \tree -> 
        printTree tree 1
insert :: Ord a => Tree (a,b) -> (a,b) -> Tree (a,b)
insert = \tree -> \(x,y) ->
    case tree of
        Nil -> Node Nil Nil (x,y) -- if empty, then insert root
        Node left right (a,b) | x < a -> Node (insert left (x,y)) right (a,b)
                              | otherwise -> Node left (insert right (x,y)) (a,b)
main = print (insert (insert (insert (insert Nil (7, "Seven")) (8, "Eight")) (6, "Six")) (5, "Five"))

Code explanation

In the code given above:

  • In line 1, we define the datatype Tree, which can either be an empty tree or a node that contains two subtrees and a value. As we can infer, Nil represents an empty tree, and a Node contains two subtrees of type Tree and a value whose type will be determined on function invocation.

  • For the sake of simplicity, we do not need to concern ourselves with the internal workings of indentation and printTree. Their purpose is to neatly print the tree when we use the insert function.

  • In lines 18–21, we make Tree an instance of the Show type class, by defining the show function that takes a Tree and returns a string.

  • We consider a tree that contains a tuple of key-value pairs such that the tree is organized as a binary search tree based on the key value. A binary search tree stores all the keys that are less than the one in the root in the left subtree and stores the rest in the right subtree. We insert new values in the tree, according to these above constraints.

  • In line 23, Ord a => Tree (a,b) -> (a,b) -> Tree (a,b) is the type annotation for our insert function. Haskell is statically typed, and every function or variable has a type. In this case, insert is a function that takes a Tree and a tuple, and returns a Tree (the tree with a newly inserted value). The Ord a ensures that the first element of the tuple should be of a totally ordered datatype.

  • Next, in line 24, we have the function definition, which shows that our function takes a Tree, a tuple (x,y), and a case expression on Tree that implements our recursive formulation of the problem.

  • In line 26, The first equation tells that if the Tree is Nil, then this means that it is an empty tree and we need to insert the root of the tree. Hence, we return Node Nil Nil (x,y).

  • In line 27, The second equation solves the general case. We have a Tree which is a Node with left and right subtrees and a key-value pair (x,y). If the key to be inserted, a, is less than x, then we return the tree where the recursive function is called at the left subtree. Otherwise, we recurse at the right subtree.

  • Finally, in line 29, we generate the whole tree by invoking our insert function and calling the printTree function to print the final tree.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)