...
/Introduction to Problem Solving Using Trie Traversal
Introduction to Problem Solving Using Trie Traversal
Get an introduction to trie traversal using depth-first search and breadth-first search.
Traversals
Trie traversal refers to visiting every trie node exactly once in a certain order. Depending upon the problem we're solving, we might have to modify the order in which the trie nodes are visited. The table below defines some widely used terms in trie traversals.
Widely Used Terms Associated with Tries
Term | Definition |
Root | The first or topmost node in a trie |
Children | Immediate nodes that are connected downward with the current node |
Parent | Immediate nodes that are connected upward with the current node |
Siblings | The nodes originating from the same node |
Descendant | A node that is reachable by repeatedly traversing from parent to child |
Ancestor | A node that is reachable by repeatedly traversing from child to parent |
Leaf | A node that does not have any child |
There are many ways to traverse tries. The most commonly used algorithms are: