What can be the maximum depth of the trie with n strings and m as the maximum sting the length?

Category: QuestionsWhat can be the maximum depth of the trie with n strings and m as the maximum sting the length?
Editor">Editor Staff asked 1 month ago

What can be the maximum depth of the trie with n strings and m as the maximum sting the length?
 
(a) log2n
 
(b) log2m
 
(c) n
 
(d) m
 
My doubt is from Trie in division 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

The correct choice is (d) m
 
Best explanation: In the trie, the strings are stored efficiently based on the common prefixes. And trie has maximum fan-out 26 if english alphabets are considered. Owing to this, the maximum depth is equal to the maximum string length.