In a skip list, how is the height of each node determined?

• A. It is the same for all nodes.
• B. It is determined by a deterministic increasing sequence.
• C. It is determined probabilistically, with a node promoted to higher levels with a fixed probability.
• D. It depends on the value stored in the node.

Answer: (C)

In a skip list, the height of each node is determined probabilistically. Each node starts at the bottom level and, with a fixed probability (commonly 1/2), is promoted to the next level. This promotion continues until a random check fails or a maximum height is reached. This randomness creates a layered structure with some nodes appearing higher than others, providing fast express paths for search operations. The height does not depend on the stored value, nor is it the same for every node or set by a deterministic sequence. This probabilistic approach yields a geometric height distribution and leads to average-case search times of O(log n).