The Height-Balanced Tree Interview Question
November 27th, 2009
Many technical interviews at companies like Microsoft and Google involve data structures. One such category of questions runs along the lines of, “Explain to me what a height-balanced tree is.” This question is usually looking to determine if you understand one of the key principles of a binary search tree, namely, that the order in which data is inserted into a binary search tree determines the shape of the tree, which in turn determines how fast the tree can be searched. So, there are several types of tree data structures which are designed to be balanced. The three types of trees you should know about are AVL trees, red-black trees, and 2-3 trees. There are many other types of balanced trees, but these three are more or less the Data Structures 101 types you should at least list. Interestingly, it is unlikely that you’d ever be asked to actually code some balanced tree routine — they are quite complex and diving into so much time in an interview where time is very limited is not an efficient approach. Anyway, if you are preparing for an interview brush up on your algorithms, especially tree algorithms.
Entry Filed under: Interviewing
Trackback this post