Trees data structures and their performance is one of the main topics to teach in a data structures course. Appreciating the importance of tree structure and tree height in software performance is an important concept to teach. In this paper, a simple and amusing activity is presented. It demonstrates to students the importance of a well-balanced tree by comparing the height of a binary search tree to a balanced (AVL) tree build upon some personal data to find the “prettiest” tree (minimum height). The activity highlights the fact that, irrelevant of your data sequence, a balanced tree guarantees a height of O(log n) and everyone “wins” the beauty contest.
Senbel, S. (2019). Teaching self-balancing trees using a beauty contest. Proceedings of the 2019 ACM Conference on Innovation and Technology in Computer Science Education. Scotland: Aberdeen. July 15. Doi: 10.1145/3304221.3325544
Proceedings of the 2019 ACM Conference on Innovation and Technology in Computer Science Education.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author. ITiCSE '19, July 15–17, 2019, Aberdeen, Scotland UK © 2019 Copyright is held by the owner/author(s).