class  ORDERED_TREE[T->COMPARABLE]
   
-- Ordered binary tree with ordered insert feature, using the natural 
-- ordering on T->COMPARABLE.  Items are in ascending order if the nodes are 
-- visited in the order "left subtree, current node, right subtree".
   
inherit  TREE[T]
   
creation  make
   
feature {ANY}
   
   insert( t: T ) is
	 -- create a new node containing t and add it to the tree in the 
	 -- correct place to maintain the ordering
      local
	 p : NODE[T]
      do
	 !!p.make(t,Void,Void)
	 if root = Void then
	    root := p
	 else
	    insert_below(p,root)
	 end
	 count := count + 1
      end -- insert
   
feature {NONE}
   
   insert_below( p,q: NODE[T] ) is
	 -- add new node p to subtree rooted at q in the correct place to 
	 -- maintain the ordering
      do
	 if p.item < q.item then
	    if q.left = Void then
	       q.set_left(p)
	    else
	       insert_below(p,q.left)
	    end
	 elseif q.right = Void then
	    q.set_right(p)
	 else
	    insert_below(p,q.right)
	 end
      end -- insert_below
   
end -- class ORDERED_TREE[T->COMPARABLE]