Table of Content

Introduction to Trie Data Structure

• Definition: A Trie (prefix tree) is a special type of tree used to store words or sequences of characters.
• Uses: Useful for fast searching, inserting, and prefix matching in applications like autocomplete, spell checkers, contact lookup, and IP routing.

Structure of a Trie

• Nodes and Edges: Similar to trees and graphs but with specific components.
• Node Components:
  • Character: The letter the node represents.
  • Children: Pointers to child nodes.
  • End of Word Flag: Indicates if the node marks the end of a valid word.

Example of Trie Structure

• Root Node: The starting point with no character, connects to child nodes.

• Example Words: "an", "ant", "and", "bat".

• Visual Representation:

          (root)
          /    \\
         a      b
        /        \\
       n          a
      / \\          \\
     d   t          t
    /    |         |
  (end) (end)    (end)
  
  

Trie Operations

• Insertion:
  • Add a new word by following the path of characters from the root, creating new nodes as needed, and marking the end node.
  • Example: Adding "ant" to the Trie.
• Search:
  • Start from the root and follow the path of characters. If the path ends at a node marked as the end of a word, the word exists.
  • Example: Searching for "ant" in the Trie.
• Deletion:
  • Follow the path of characters to the end node, unmark the end node, and backtrack to delete nodes without children.
  • Example: Deleting "ant" from the Trie.

Applications of Trie

• Autocomplete: Suggests completions for partial words.
• Spell Checkers: Checks if words exist and suggests corrections.
• Contact Lookup: Finds relevant contacts based on input.