netflix's blog

Keyword Tree / Trie data structure implementation
By netflix, history, 6 years ago, In English

Whenever I solve a question using the Keyword Tree / Trie data-structure, I implement it using pointers. But I have seen many programmers implementing trie using arrays.

What are the downsides of using the Pointers implementation (if at all) , as compared to the Arrays implementation ?

Pointers Implementation Code

Arrays Implementation Code

Happy Coding !

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Pointers dynamically allocate memory which takes a bit more time. In array implementation you already have a fixed size declared- this saves time. So you see there is a trade-off between time and memory. Both are equally efficient under normal circumstances. Only when the constraints are too tight you may need to choose between the two.

→ Reply