Data Structures and Algorithms
Digital Assignment
Implementation of disease
checker using Trie data structure
Madhav Nanda: 23BCE2248
Mohammed Laamih: 23BCE2220
Mohammed Nadeem: 23BCE2091
Overview:
The main aim of this project is to create a “disease checker”. The system
takes symptoms as input, and provides us with a disease, by keeping a count
of the number of matching symptoms. The disease with the highest ‘count’
will be displayed as the output. This project utilizes the Trie data structure to
implement operations like adding a disease, updating the symptoms,
searching for the disease and so on.
Introduction
Through this project, we seek to enable the creation of an automated patient
experience. Patients can input their symptoms into the system and can find
out the disease they are most likely to have. Additionally, prescriptions for
the same is recommended by the system. However, if the system is unable
to predict the disease with accuracy, it directs the patient to an available
doctor for a checkup.
To achieve this, we use Trie data structure. A “Trie” is a tree-like data
structure that is primarily used to store strings, especially for handling
sequences such as words in a dictionary. It is widely used in applications
requiring efficient information retrieval, such as autocomplete and spell-
check functionalities. Trie’s are particularly efficient for handling prefix-based
searches.
Key features of a Trie –
Prefix-Based Organization: Each level in a Trie represents a character in
a string, making it highly efficient for prefix-based operations.
Character Nodes: Each node in a Trie represents a character of a string.
End-of-Word Markers: Some nodes have markers to indicate the end of
a word.
Efficient search: Trie’s offer fast lookups, insertions, and deletions for
strings with common prefixes, often with complexity proportional to the
length of the word being inserted or searched.
Trie Structure –
Each node has:
A set of children nodes corresponding to subsequent characters in
strings.
An end-of-word flag to indicate if a particular node marks the end of a
valid word.
Why use a Trie?
Efficient prefix based matching enables features like autocomplete and
suggestions. This is very useful as there may be symptoms that are
long and complex, and users may benefit from partial matches.
Fast lookup and retrieval: For symptom recognition, Trie’s provide very
fast lookup times proportional to the length of the symptom string.
Given that symptoms may share common prefixes, a Trie structure can
quickly retrieve all possible symptom matches with minimal processing
time.
Memory Efficient with Shared Prefixes: Since many medical terms
share similar prefixes, a Trie compresses these shared prefixes, which
reduces the memory footprint compared to structures like hash tables
and arrays, where each string is stored independently.
Trie Operations –
1. Insertion (insertSymptom())
This function is used to accept a symptom (String)
as input.
The function then associates the symptom to a
disease and a prescription.
Illustration:
Source Code:
2. Searching (searchSymptom())
This function takes a symptom as input and
searches for the symptom in the Trie.
It also updates the symptom count, to calculate the
accuracy with which the diagnosis was made.
Illustration:
Source Code:
3. Function to diagnose the disease (diagnoseDisease())
The function performs a diagnosis and provides a
disease based on symptoms provided and symptom
count.
The function then either provides a prescription or
directs the patient to a doctor if the accuracy of the
diagnosis is lower than 50%.
Source Code:
Final Source Code:
Note: Please enable editing to view text file.
Time Complexities:
Operation Function Time Explanation
Complexity
Create a new Trie createNode() O(1) Constant time for
node memory
allocation and
initialization.
Insert a symptom insertSymptom() O(n) Inserting all
symptoms takes
linear time in
terms of total
input size n, as
each character is
processed once
inserted
Search for a searchSymptom( O(n) In the worst
symptom ) case, all input
characters are
traversed during
searches.
Disease diagnoseDisease O(n) Checking
diagnosis () matched
diseases requires
linear time in n
because match
counts are based
on total
symptom
occurrences.
YouTube link: https://www.youtube.com/watch?
v=kUG7IYVC4JU
