Skip to main content

Trie data structure implementation.

Project description

Documentation Status (latest) Documentation Status (stable)

pygtrie is a Python library implementing a trie data structure.

Trie data structure, also known as radix or prefix tree, is a tree associating keys to values where all the descendants of a node have a common prefix (associated with that node).

The trie module contains Trie, CharTrie and StringTrie classes each implementing a mutable mapping interface, i.e. dict interface. As such, in most circumstances, Trie could be used as a drop-in replacement for a dict, but the prefix nature of the data structure is trie’s real strength.

The module also contains PrefixSet class which uses a trie to store a set of prefixes such that a key is contained in the set if it or its prefix is stored in the set.


  • A full mutable mapping implementation.
  • Supports iterating over as well as deleting a subtrie.
  • Supports prefix checking as well as shortest and longest prefix look-up.
  • Extensible for any kind of user-defined keys.
  • A PrefixSet supports “all keys starting with given prefix” logic.
  • Can store any value including None.


To install pygtrie, run:

pip install pygtrie

Or download the sources and save file with your project.

Upgrading from 0.9.x

The 1.0 release introduced backwards incompatibility in naming. The module has been renamed from trie to pygtrie. Fortunately, updating scripts using pygtrie should boil down to replacing:

from pytrie import trie


import pygtrie as trie

Version History

2.3: 2018/08/10

  • New walk_towards method allows walking a path towards given a node with given key accessing each step of the path. Compared to prefixes method, steps for nodes without assigned values are
  • Fix to PrefixSet.copy not preserving type of backing trie.
  • StringTrie now checks and explicitly rejects empty separators. Previously empty separator would be accepted but lead to confusing errors later on. [Thanks to Waren Long].
  • Various documentation improvements, Python 2/3 compatibility and test coverage (python-coverage reports 100% o/).

2.2: 2017/06/03

  • Fixes to breaking on Windows which prevents installation among other things.

2.1: 2017/03/23

  • The library is now Python 3 compatible.
  • Value returend by shortest_prefix and longest_prefix evaluates to false if no prefix was found. This is in addition to it being a pair of Nones of course.

2.0: 2016/07/06

  • Sorting of child nodes is disabled by default for better performance. enable_sorting method can be used to bring back old behaviour.
  • Tries of arbitrary depth can be pickled without reaching Python’s recursion limits. (N.B. The pickle format is incompatible with one from 1.2 release). _Node’s __getstate__ and __setstate__ method can be used to implement other serialisation methods such as JSON.

1.2: 2016/06/21 [pulled back from PyPi]

  • Tries can now be pickled.
  • Iterating no longer uses recursion so tries of arbitrary depth can be iterated over. The traverse method, however, still uses recursion thus cannot be used on big structures.

1.1: 2016/01/18

  • Fixed PyPi installation issues; all should work now.

1.0: 2015/12/16

  • The module has been renamed from trie to pygtrie. This could break current users but see documentation for how to quickly upgrade your scripts.
  • Added traverse method which goes through the nodes of the trie preserving structure of the tree. This is a depth-first traversal which can be used to search for elements or translate a trie into a different tree structure.
  • Minor documentation fixes.

0.9.3: 2015/05/28

  • Minor documentation fixes.

0.9.2: 2015/05/28

  • Added Sphinx configuration and updated docstrings to work better with Sphinx.

0.9.1: 2014/02/03

  • New name.

0.9: 2014/02/03

  • Initial release.

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Filename, size & hash SHA256 hash help File type Python version Upload date
pygtrie-2.3.tar.gz (29.6 kB) Copy SHA256 hash SHA256 Source None Aug 10, 2018

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page