Question

Skip lists are similar to which of the following datastructure?

(a) stack

(b) heap

(c) binary search tree

(d) balanced binary search tree

Origin of the question is Skip List topic in portion Types of Lists of Data Structures & Algorithms I

This question was posed to me in a job interview.

Answer 1

The correct choice is (d) balanced binary search tree

The explanation is: Skip lists have the same asymptotic time complexity as balanced binary search tree. For a Balanced Binary Search Tree, we skip almost half of the nodes after one comparison with root element. The same thing done in the skip lists. Hence skip lists are similar to balanced Binary search trees.