How much space does construction of suffix tree takes?

Category: QuestionsHow much space does construction of suffix tree takes?
Editor">Editor Staff asked 1 month 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 1 month 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.