I don't know what your object looks like exactly, but you might want to 
look a little at Purely Functional
Data Structures by Chris Okasaki (should be available online if you do 
search google).

For example, when you make a binary search tree structure in a 
functional manner, to insert, you have to
duplicate the path to the newly inserted node.  This doesn't require 
cloning the whole tree, though, so you
only need to clone log n objects.

Seems like this strategy would work for your object (and I believe there 
are other examples in the book of
similar operations).  You probably need a similar algorithm.

- Dan

P.S.: a little Ruby to get the ideas flowing (written in a more 
functional style out of ease)

class Node
    attr_reader :v, :l, :r
    def initialize(v, l, r)
       @value = v
       @l = l
       @r = r
    end
end

def insert(value, tree)
    if tree.nil?
       new Node value, nil, nil
    elsif value < tree.v
       Node.new(tree.v, insert value tree.l, tree.r)
    else
       Node.new(tree.v, tree.l, insert value tree.r)
    end
end