gistfile1.e

add_node(item : G; root : BIN_NODE[G]) is
    local
        previous_node, current_node, new_node : BIN_NODE[G]
    do
        if root = Void then
            -- The trivial case, creating the root of the tree
            -- with no subtrees
            create root
            root.build(item, Void, Void)
            count := 1
        else
            -- The non-trivial case, in which you have to
            -- traverse the tree to find the right spot 
            -- for the new node.
            from
                current_node := root
            until
                current_node = Void or else item = current_node.value
            loop -- Find the right place to put the new item
                previous_node := current_node

                if item < current_node.value then
                    current_node := current_node.left
                else if item > current_node.value then
                    current_node := current_node.right
                end
            end
            if current_node /= Void then -- Don't allow duplicates
                -- Create the new node, with no subtrees
                create new_node
                new_node.build(item, Void, Void)

                -- Decide whether it's a left subtree or a right subtree
                if item < previous_node.value then
                    previous_node.left_set(new_node)                    
                else if item > previous_node.value then
                    previous_node.right_set(new_node)
                end

                count := count + 1
            end
        end
    end

array2bst(a : ARRAY[G]; tree : BST[G]) is
    require
        a /= Void and tree /= Void
    local
        k : INTEGER
    do
        from
            k := a.lower
        until
            k = a.upper
        loop
            add_node(a.item(k), tree)
        end
    end