Misconceptions and concept inventory questions for binary search trees and hash tables

In this paper, we triangulate evidence for five misconceptions concerning binary search trees and hash tables. In addition, we design and validate multiple-choice concept inventory questions to measure the prevalence of four of these misconceptions. We support our conclusions with quantitative analysis of grade data and closed-ended problems, and qualitative analysis of interview data and open-ended problems. Instructors and researchers can inexpensively measure the impact of pedagogical changes on these misconceptions by using these questions in a larger concept inventory.