java polymorphic binary search tree

Question

how can i implement a polymorphic binary search tree (that makes use of EmptyTree and NonEmptyTree) without using downcasting or class checking?

Answer 1

Instead of using null to represent non-existent children, use an instance of EmptyTree. You will have to create two node implementations NonEmptyTree that behaves like you would expect and EmptyTree that behaves like an empty tree. Most likely, you will need to make operations that mutate the tree (e.g. inserting nodes) return the resulting tree instead of simply having side-effects (so that, for example, insertion into an EmptyTree yields an instance of NonEmptyTree which then replaces the old EmptyTree).