I wander if the nerds that invented the trees data structure thought about standards when they invented it. I don’t think they did.

Don’t get me wrong! They are innovators who changed the computer science scene and revolutionized the industry by inventing such data structure that we ease some solutions to some problems. The trees data structure lets us search for keys and values faster. And they also have so many advantages in terms of deletions and insertions, and searching. They are prototypes to forms like AVL TREE, sets, multi sets, and dictionaries. Plus, the concept of the tree alone makes us think about other interesting and challenging concepts in computer science in a more intuitive way. For example, the study of trees inevitably introduces the programmer to hard-to-grasp concepts like recursion, depth-first search, breadth-first search, data structure traversal, mathematical induction, fractals, to mention a few.

The only problem with the data structure is that its implementation varies. And this can be bewildering sometimes. For example, I have read in some encyclopedias and textbooks that trees cannot have duplicates. However, some other sites and textbooks claim otherwise. The stanford library at cslibrary.stanford.edu gives some examples of cloning a tree within a tree– that is, making duplicates in the tree. In particular, they claim that duplicates of a value should be added to the left of that value such that if a, b, c represent the left subtree, root, and right subtree respectively, if a new node d (b==d or a ==d or c==d) where d is equal in value to one of the nodes already present in the tree, d, the new node, is added to the left of the node equal in value. This contradicts with other textbooks that claim that binary search trees should not have duplicates values. To further perplex us, the wikipedia article on binary trees and BST’s straddle between both views. In fact, it is self-contradictory in how it says that trees should have duplicates in a section of the article but still in another section says that trees should never contain duplicates. I’m perplexed. I need clarification on this. Which should I follow. Should I implement trees that allow duplicates or not. Which implementation is better? And how do I know?

Or maybe it just happens that we can make our own implementation. Or do whatever we like in computer science concerning data structures in CS. That’s why I love computer science. We can blaze the trail!

So I think for now I will just stick with the BST that allows duplicates because there are more interesting problems I can solve on such BST. GOOD WAY TO PRACTICE FOR THE ACM!