Knowing your roots
Joel C. Adams · ACM SIGCSE Bulletin · 1996
By applying object-oriented design to the definition of a binary search tree, Berman and Duvall [1] designed a data structure comprised of three classes: (i) an Empty bst class to model empty binary search trees, (ii) a NonEmpty bst class to model non-empty binary search trees, and (iii) a bst base class for common attributes of Empty bst and NonEmpty bst objects. That paper noted the problem of inserting new values into such a structure: since insertions occur at an Empty bst object, an Empty bst would have to "turn into" a NonEmpty bst ; a behavior beyond the capabilities of the classes in most languages.This paper presents three C++ solutions to the insertion problem in their order of development. The first solution uses a procedural programming technique, with the second and third solutions shifting to a more object-oriented approach. This chronology illustrates the author's ongoing battle to shift from procedural to object-oriented thinking.