Trie-Based Search Engine (C++)

A high-performance Trie-based search engine implemented in C++, designed for efficient word indexing, prefix search, and autocomplete functionality. This project demonstrates practical use of Data Structures & Algorithms (DSA) in scalable search operations.

---

Overview

The project implements a Trie (Prefix Tree) from scratch to handle:

• Word insertion
• Full-word search
• Prefix search
• Autocomplete suggestions

Unlike hash-based approaches, Tries enable efficient prefix queries in O(L) time per operation, where L is the query length.

---

Features

• Custom Trie (Prefix Tree) implementation
• Fast insert, search, and prefix lookup
• Autocomplete using Depth-First Search (DFS)
• Optimized for scalability and memory efficiency
• Clean, modular, interview-ready C++ code

---

Technical Details

• Language: C++
• Data Structure: Trie (Prefix Tree)
• Algorithm: DFS for autocomplete
• Time Complexity:
  • Insert: O(L)
  • Search: O(L)
  • Prefix Search: O(L)
  • Autocomplete: O(L + K) (K = number of suggestions)
• Space Complexity: O(N × L)
  (N = number of words, L = average word length)

---

Project Structure

trie-search-engine/
│
├── Trie.h
├── Trie.cpp
└── main.cpp

---

How to Run

Prerequisites

• C++ compiler (g++)
• Terminal / PowerShell / CMD

Check compiler:

g++ --version

Steps (Windows)

Navigate to project directory:

cd path/to/trie-search-engine

Compile:

g++ main.cpp Trie.cpp -o trie_search

On Windows, this creates trie_search.exe.

Run:

Windows (PowerShell):

.\trie_search.exe

Windows (CMD):

trie_search.exe

Sample Output

1 0 1 banana bat ball batsman