= Solution
Insert down the unique search route, leaving equal elements unchanged:
``
insert :: Ord a => a -> Tree a -> Tree a
insert q Empty = Tree Empty q Empty
insert q t@(Tree l x r) = case compare q x of
LT -> Tree (insert q l) x r
EQ -> t
GT -> Tree l x (insert q r)
``
The <binary search tree> ordering determines the only child in which a missing query can belong. The recursive call preserves that child's ordering bounds, and the other child is shared. Thus the output represents the original <set> with `q` added, with duplicates suppressed. Its <time complexity> and newly allocated route length are $O(h+1)$; it makes no balancing guarantee.
Back to article page
