In the previous post, we implemented a simple Binary Search Tree(BST) and added functionality to add/search and traverse binary tree. In this post we will add functionality to remove keys from BST. Deleting a key in binary tree is little difficult, to delete a node from tree we need to consider following cases.

1. The Tree is Nil, Then after deleting resulting tree is Nil.
2. If the Node has matching key and it’s left and right children are Nil, then resulting tree is Nil tree.
3. If nodes right children in Nil
   • If key matches the resulting tree is left tree.
   • else if node’s key is bigger then try deleting search key from left tree
   • otherwise search key do not exists in tree, tree remains as it is.
4. Symmetric to case 3, for left children.
5. If node does not have matching key, and node’s key is bigger than search key, then try deleting from left subtree, else try deleting from right subtree.
6. The complex case is when, Node key is matching and it’s right and left subtrees are not Nil, In this case we will pick up maximum key from left subtree and replace it with current node, and delete maximum key from the left tree.

The resulting Haskell implementation is below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

delete :: (Ord a) => Tree a -> a -> Tree a
-- case 1
delete Nil _ = Nil
-- case 2
delete (Node a Nil Nil) key
  | a == key = Nil
  | otherwise = Node a Nil Nil
-- case 3
delete (Node a Nil right) key
  | a == key  = right
  | a < key = Node a Nil (delete right key)
  | otherwise = Node a Nil right
-- case 4
delete (Node a left Nil) key
  | a == key = left
  | a > key = Node a (delete left key) Nil
  | otherwise = Node a left Nil
-- case 5 and 6  
delete (Node a left right) key
  | a == key = Node maxLeft (delete left maxLeft) right
  | a > key  = Node a (delete left key) right
  | otherwise = Node a left (delete right key)
  where
    maxLeft = maxElemNonNil left
    maxElemNonNil (Node a _ Nil) = a
    maxElemNonNil (Node a _ left) = maxElemNonNil left

A ghci session to test delete function.

1
2
3
4
5
6

*Main> let a = [10, 2, 13, 5, 18, 28, 27, 95, 73, 75, 49, 93]
*Main> let tree = list2Tree a
*Main> tree
Node 10 (Node 2 Nil (Node 5 Nil Nil)) (Node 13 Nil (Node 18 Nil (Node 28 (Node 27 Nil Nil) (Node 95 (Node 73 (Node 49 Nil Nil) (Node 75 Nil (Node 93 Nil Nil))) Nil))))
*Main> delete tree 73
Node 10 (Node 2 Nil (Node 5 Nil Nil)) (Node 13 Nil (Node 18 Nil (Node 28 (Node 27 Nil Nil) (Node 95 (Node 49 Nil (Node 75 Nil (Node 93 Nil Nil))) Nil))))

I have just started to learn Haskell from various sources, such as Lean You Haskell and Real World Haskell. After reading few chapters, this is my first attempt to code a Binary Search Tree in Haskell, supporting add, search and traverse operation.

A node is Binary Search Tree contains a comparable key and left and right subtrees, which can be empty. The left tree contains smaller keys and right tree contains bigger keys that the node’s key.

The Tree is recursively defined as a Nil tree i.e a empty tree, or a Node with key, left and right subtrees. This recursive data definition is specified in Haskell easily using abstract data type as follows.

1
2
3

data Tree a = Node a (Tree a) (Tree a)
      | Nil
      deriving(Show, Eq)

Insert

To add a key in a BST is easy, if tree is empty, then after adding one key is equivalent of creating a new Node with left and right tree set to Nil, and data set to the key.

If new key is smaller than current node’s key then add a key to the left tree, else add the key to right tree.

The following function implements the insert method which takes a Tree and key to be added to the tree. If key is already present in the Tree then this function returns the same Tree, else returns a new Tree with key added. As Haskell is purely functional language, we can not modify original tree, instead it creates a new tree every time a key is added to the tree.

1
2
3
4
5
6
7
8
9
10

{-
Add a node to Tree, If element already present in the Tree,
then it is ignored.
-}
insert :: (Ord a) => Tree a -> a -> Tree a
insert Nil elem = Node elem Nil Nil
insert (Node val left right) elem
  | elem < val = Node val (insert left elem) right
  | elem > val = Node val left (insert right elem)
  | otherwise = Node val left right

If we want to add bunch of keys to the Tree, then built in fold function can be used, A one line function to add list of keys to the Tree is

1

list2Tree = foldl insert Nil

Let’s try these functions in ghci session.

1
2
3
4

*Main> let a = [30, 10, 45, 4, 8, 69, 85]
*Main> let tree = list2Tree a
*Main> tree
Node 30 (Node 10 (Node 4 Nil (Node 8 Nil Nil)) Nil) (Node 45 Nil (Node 69 Nil (Node 85 Nil Nil)))

Inserting a new node

1
2
3
4
5

*Main> tree
Node 30 (Node 10 (Node 4 Nil (Node 8 Nil Nil)) Nil) (Node 45 Nil (Node 69 Nil (Node 85 Nil Nil)))
*Main> let newtree =  insert tree 35
*Main> newtree
Node 30 (Node 10 (Node 4 Nil (Node 8 Nil Nil)) Nil) (Node 45 (Node 35 Nil Nil) (Node 69 Nil (Node 85 Nil Nil)))

Search

Searching in binary tree starts at the root node and then recursively follow left or right branch until we reach at empty tree (Nil) or search key is found. The function is split into two cases.

• If current root is Nil then we have reached at the leaf node, and element does not exists in the tree, so we return false. (line 3)
• If current root is not Nil and key matches then element present in the tree, else we recursively call search with left or right node depending on value of key. (line 5,6,7)

1
2
3
4
5
6
7

{- Search a tree -}
search :: (Ord a) => Tree a -> a -> Bool
search Nil _ = False
search (Node elem left right) a
  | elem == a = True
  | elem > a  = search left a
  | otherwise = search right a

Lets try out search on some of the keys.

1
2
3
4

*Main> search newtree 85
True
*Main> search newtree 80
False

Traversing elements in the tree.

Apart from breath first and depth first traversal, binary tree can be traverse in pre-order, post-order and in-order traversal. The in-order traversal visit elements in the sorted order. Following is the implementation in Haskell which returns a list of element in order they are visited in the traversal.

• Pre-order
  • Visit the root.
  • Traverse the left subtree.
  • Traverse the right subtree.

1
2
3
4
5

{- Pr-eorder tree traversal -}
preOrder :: Tree a -> [a]
preOrder Nil = []
preOrder (Node a left right) =
  a : preOrder left ++ preOrder right

• In-order (symmetric)
  • Traverse the left subtree.
  • Visit the root.
  • Traverse the right subtree.

1
2
3
4
5

{- In-order tree traversal -}
inOrder :: Tree a -> [a]
inOrder Nil = []
inOrder (Node a left right) =
  inOrder left ++ [a] ++ inOrder right

• Post-order
  • Traverse the left subtree.
  • Traverse the right subtree.
  • Visit the root.

1
2
3
4
5

{- Post-order tree traversal -}
postOrder :: Tree a -> [a]
postOrder Nil = []
postOrder (Node a left right) =
  postOrder left ++ postOrder right ++ [a]

Lets try these functions, see that in-order traversal of BST gives element in sorted order.

1
2
3
4
5
6
7
8

*Main> preOrder newtree
[30,10,4,8,45,35,69,85]

*Main> postOrder newtree
[8,4,10,35,85,69,45,30]

*Main> inOrder newtree
[4,8,10,30,35,45,69,85]

Find Max and Min

The maximum element is the right most element in the tree, i.e keep following right branch until node’s right branch is Nil. That node has the maximum value of the key.

1
2
3
4

maxElem :: Tree a -> Maybe a
maxElem Nil = Nothing
maxElem (Node elm _ Nil) = Just elm
maxElem (Node a _ right) = maxElem right

Similarly the minimum element is found by following left branch.

1
2
3
4

minElem :: Tree a -> Maybe a
minElem Nil = Nothing
minElem (Node a Nil _) = Just a
minElem (Node _ left _) = minElem left

Let’s try this out in ghci.

1
2
3
4
5

*Main> minElem newtree
Just 4

*Main> maxElem newtree
Just 85

That’s it for now, In this post we have implemented a simple binary tree supporting basic operations except delete for which I am planing to write a separate post. Haskell language is very concise, and because of pattern matching and good support for writing recursive functions , most of the recursive algorithms on binary tree are translated directly into Haskell without much effort.

The code for binary search tree is available on Github