# Binary Search Trees

Let us implement in julia 0.6.0 a binary search tree to store integers. Each node is either of type Nil or of type bst, as declared below. Type Nil is used a null pointer. We use type union MayBe to hold either a Nil() or a bst. At the start the tree is empty so it is initialized to Nil(). Removing the type declaration from the data element should be sufficient to store datatypes for which a comparator is implemented.

type Nil end
MayBe{T} = Union{T,Nil}

type  bst
data::Int
left::MayBe{bst}
right::MayBe{bst}
end

global root = Nil()                # root of the BST


## Find

Order property states that at every node, the left sub tree contains smaller values, and the right subtree contains larger values. So, it is straightforward to branch, given a key and the value stored at a node. Below is a recursive implementation of find

function find(node::MayBe{bst}, key::Int)
if (typeof(node) == Nil)
return false
end

if (node.data == key)
return true
end

if (key < node.data)
find(node.left, key)
else
find(node.right, key)
end
end


## Insert

We assume that duplicates are not allowed. To insert a node we branch as in the case of find. Once we have located the pointer (identified by type Nil), we attach a new single node bst object. If the insertion occurs in the left subtree then the left pointer of the node is updated. The right pointer is updated if the insertion occurs in the right subtree. We return the modified tree in each recursive step. This has to do with how arguments are passed by value in julia.

function ins(node::MayBe{bst}, d::Int)    # insert d in the BST rooted at node

if (typeof(node)==Nil)
node = bst(d, Nil(), Nil())          # attach a new BST with data d
return node
end

if (d == node.data)
return node            # d already in the tree, no insertion
end

if (d < node.data )      # check whether insert is in left/right subtree
node.left = ins(node.left, d)
else
node.right = ins(node.right, d)
end
return node         # reference needed to reassign the node

end


The sequence of insertions below (in array A) should give a balanced binary search tree.

global root = Nil()
A = [4,2,6,1,3,5,7]
for i=1:length(A)
root = ins(root,A[i])      # note the assignment to root, BST updated
println(root)
end

bst(4, Nil(), Nil())
bst(4, bst(2, Nil(), Nil()), Nil())
bst(4, bst(2, Nil(), Nil()), bst(6, Nil(), Nil()))
bst(4, bst(2, bst(1, Nil(), Nil()), Nil()), bst(6, Nil(), Nil()))
bst(4, bst(2, bst(1, Nil(), Nil()), bst(3, Nil(), Nil())), bst(6, Nil(), Nil()))
bst(4, bst(2, bst(1, Nil(), Nil()), bst(3, Nil(), Nil())), bst(6, bst(5, Nil(), Nil()), Nil()))
bst(4, bst(2, bst(1, Nil(), Nil()), bst(3, Nil(), Nil())), bst(6, bst(5, Nil(), Nil()), bst(7, Nil(), Nil())))


## Delete

Helper function min find the minimum value in the right subtree at any given node. We use this minimum value in the delete function.

function min(node::MayBe{bst})  # returns Int, never called on empty BST
while (typeof(node.left) != Nil)
node = node.left
end
return node.data               # left most element
end


To delete an element we proceed as in find. If the element is not found, and we end up with a Nil type then return the original tree. Otherwise, three cases are to be considered.

• The node to be deleted is a leaf node: in this case, we return the Nil(), which is assigned to the appropriate subtree of the parent, thereby deleting the node.

• The node to be deleted has a single child: in this case return either the left or the right subtree.

• The node has two children. We find the minimum element in the right subtree, and delete it from the right subtree. The resulting subtree is now the right child of the node, and the value at the node can be replaced by the minimum value in the right subtree.

function del(node::MayBe{bst}, d::Int)
if (typeof(node)==Nil)
return node
end

if ((d == node.data) && (typeof(node.left) == Nil) && (typeof(node.right) == Nil))
return Nil()                   # node to be deleted is a leaf
end

if ((d == node.data) && (typeof(node.left) == Nil))   # node to be deleted has one child
return node.right
end

if ((d == node.data) && (typeof(node.right) == Nil)) # node to be deleted has one child
return node.left
end

# node to be deleted has two children
if ((d == node.data) && (typeof(node.left) != Nil) && (typeof(node.right) != Nil))
m = min(node.right)            # find the min in the right subtree
node = del(node, m)            # delete it recursively
node.data = m                  # copy the min to the current node
return node
end

if (d < node.data)
node.left = del(node.left, d)
else
node.right = del(node.right, d)
end
return node
end


The sequence of deletions below should give an empty tree.

A = [4,2,6,1,3,5,7]
for i=1:length(A)
root = del(root, A[i])
println(root)
end

bst(5, bst(2, bst(1, Nil(), Nil()), bst(3, Nil(), Nil())), bst(6, Nil(), bst(7, Nil(), Nil())))
bst(5, bst(3, bst(1, Nil(), Nil()), Nil()), bst(6, Nil(), bst(7, Nil(), Nil())))
bst(5, bst(3, bst(1, Nil(), Nil()), Nil()), bst(7, Nil(), Nil()))
bst(5, bst(3, Nil(), Nil()), bst(7, Nil(), Nil()))
bst(5, Nil(), bst(7, Nil(), Nil()))
bst(7, Nil(), Nil())
Nil()


## Average times

We can also plot the time it takes for random insertions and then random deletions. The insertions are in blue and the deletions are in yellow.

using PyPlot

size = 10000
y=zeros(size)

inp = randperm(size)

root =Nil()
ctr = 1
for j in inp
y[ctr] = @elapsed    root = ins(root,j)
ctr = ctr + 1
end

p = plot( y)

ctr = size
for j in inp[1:size-1]
y[ctr] = @elapsed    root = del(root,j)
ctr = ctr - 1
end

p= plot( y)

#for i=1:size
#     y[i] = @elapsed    root = ins(root,i)
#end

#p = plot(y)


The code is available here.