Editor">
Editor Staff asked 5 months ago
Editor Staff asked 5 months ago
How much space does construction of suffix tree takes?
(a) O (log M)
(b) Exponential to Length of Tree
(c) O (M!)
(d) Linear to Length of Tree
Origin of the question is Suffix Tree topic in section Trie of Data Structures & Algorithms I
This question was addressed to me at a job interview.
1 Answers
Editor">Editor Staff answered 5 months ago
Editor Staff answered 5 months ago
Correct option is (d) Linear to Length of Tree
The explanation is: Suffix tree is also known as PAT tree or position tree. It is a compressed search tree or prefix tree in which keys contain the suffix of text values as the text position. It allows fast string operation. Total space taken for construction of a suffix tree is linear to the length of the tree.
