Editor">
Editor Staff asked 5 months ago
Editor Staff asked 5 months 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 5 months ago
Editor Staff answered 5 months 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.
