Introduction to Problem Solving Using Trie Traversal
Explore trie traversal techniques including depth-first and breadth-first search to understand how to visit and manipulate trie nodes. Gain skills to solve problems like sorting, searching, adding, or deleting data in tries using order-specific traversal methods.
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:
Depth-first search
Breadth-first search ...