How to implement a Binary Search Tree in Julia?

Question

I am trying to implement BST in Julia, but I encountered problem when I call insert function. When I try to create new node, the structure stays unchanged.

My code:

type Node
    key::Int64
    left
    right
end

function insert(key::Int64, node)
    if node == 0
        node = Node(key, 0, 0)
    elseif key < node.key
        insert(key, node.left)
    elseif key > node.key
        insert(key, node.right)
    end
end

root = Node(0,0,0)
insert(1,root)
insert(2,root)

I also tried to change zero to nothing. Next version which I tried is with defined datatypes in Node, but when I try to call insert with nothing value(similar to C Null) it gave me error.

Thank for answer.

Answer 1

The code has a number of issues. One is that it is not type stable, left and right could contain anything. The other is that setting the local variable node inside the insert function will not affect change anything. A stylistic issue, functions that modify their arguments generally have a ! as the last character in the name, such as insert!, push! setindex!.

I think the following should work:

type BST
    key::Int
    left::Nullable{BST}
    right::Nullable{BST}
end

BST(key::Int) = BST(key, Nullable{BST}(), Nullable{BST}())
BST() = BST(0)

function Base.push!(node::BST, key)
    if key < node.key
        if node.left.isnull
            node.left = BST(key)
        else
            push!(node.left.value, key)
        end
    elseif key > node.key
        if node.right.isnull
            node.right = BST(key)
        else
            push!(node.right.value, key)
        end
    end
end

root = BST()
push!(root, 1)
push!(root, 2)

This version overloads the Julia push! function, and uses the Nullable type so that it can distinguish between a leaf node and where it needs to continue searching to find where to insert the key. This is a recursive definition, and is not optimized, it would be much faster to do it with loops instead of recursive.