• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Trie Dictionary

April 14, 2015 by Dhaval Dave

Trie also called prefix tree (as they can be searched by prefixes).
The term trie comes from retrieval.
In the example shown, keys are listed in the nodes and values below them. Each complete English word has an arbitrary integer value associated with it.
A trie can be seen as a deterministic finite automaton without loops. Each finite language is generated by a trie automaton, and each trie can be compressed into a DAFSA.
It is not necessary for keys to be explicitly stored in nodes. (In the figure, words are shown only to illustrate how the trie works.)

tries
tries
struct trie_node
{
 int value; /* Used to mark leaf nodes */
 trie_node_t *children[ALPHABET_SIZE];
};

Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
 
// Alphabet size (# of symbols)
#define ALPHABET_SIZE (26)
// Converts key current character into index
// use only 'a' through 'z' and lower case
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')
 
// trie node
typedef struct trie_node trie_node_t;
struct trie_node
{
 int value;
 trie_node_t *children[ALPHABET_SIZE];
};
 
// trie ADT
typedef struct trie trie_t;
struct trie
{
 trie_node_t *root;
 int count;
};
 
// Returns new trie node (initialized to NULLs)
trie_node_t *getNode(void)
{
 trie_node_t *pNode = NULL;
 
 pNode = (trie_node_t *)malloc(sizeof(trie_node_t));
 
 if( pNode )
 {
 int i;
 
 pNode->value = 0;
 
 for(i = 0; i < ALPHABET_SIZE; i++)
 {
 pNode->children[i] = NULL;
 }
 }
 
 return pNode;
}
 
// Initializes trie (root is dummy node)
void initialize(trie_t *pTrie)
{
 pTrie->root = getNode();
 pTrie->count = 0;
}
 
// If not present, inserts key into trie
// If the key is prefix of trie node, just marks leaf node
void insert(trie_t *pTrie, char key[])
{
 int level;
 int length = strlen(key);
 int index;
 trie_node_t *pCrawl;
 
 pTrie->count++;
 pCrawl = pTrie->root;
 
 for( level = 0; level < length; level++ )
 {
 index = CHAR_TO_INDEX(key[level]);
 if( !pCrawl->children[index] )
 {
 pCrawl->children[index] = getNode();
 }
 
 pCrawl = pCrawl->children[index];
 }
 
 // mark last node as leaf
 pCrawl->value = pTrie->count;
}
 
// Returns non zero, if key presents in trie
int search(trie_t *pTrie, char key[])
{
 int level;
 int length = strlen(key);
 int index;
 trie_node_t *pCrawl;
 
 pCrawl = pTrie->root;
 
 for( level = 0; level < length; level++ )
 {
 index = CHAR_TO_INDEX(key[level]);
 
 if( !pCrawl->children[index] )
 {
 return 0;
 }
 
 pCrawl = pCrawl->children[index];
 }
 
 return (0 != pCrawl && pCrawl->value);
}
 
// Driver
int main()
{
 // Input keys (use only 'a' through 'z' and lower case)
 char keys[][8] = {"the", "a", "there", "answer", "any", "by", "bye", "their"};
 trie_t trie;
 
 char output[][32] = {"Not present in trie", "Present in trie"};
 
 initialize(&trie);
 
 // Construct trie
 for(int i = 0; i < ARRAY_SIZE(keys); i++)
 {
 insert(&trie, keys[i]);
 }
 
 // Search for different keys
 printf("%s --- %s\n", "the", output[search(&trie, "the")] );
 printf("%s --- %s\n", "these", output[search(&trie, "these")] );
 printf("%s --- %s\n", "their", output[search(&trie, "their")] );
 printf("%s --- %s\n", "thaw", output[search(&trie, "thaw")] );
 
 return 0;
}

code courtesy : geeksforgeeks.org & Venki

Similar Articles

Filed Under: Amazon Interview Question, Interview Questions, Microsoft Interview Questions, problem Tagged With: tree, Trie

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Search element in a matrix with all rows and columns in sorted order

Advanced SQL Injection

Maximum difference between two elements s.t larger element appears after the smaller number

LeetCode: Binary Tree Maximum Path Sum

Subset Sum Problem Dynamic programming

Find shortest distances between every pair of vertices ( Dynamic Programming Floyd Warshall Algorithm)

Facebook Interview Question : Interleave List

SAP Hiring Off-Campus General Aptitude

Urban Ladder Written Test.

Check if an array has duplicate numbers in O(n) time and O(1) space

Spanning Tree

CodeChef Code SGARDEN

Find next greater number with same set of digits

Connect n ropes with minimum cost

Edit Distance ( Dynamic Programming )

Find position of the only set bit

Apriori algorithm C Code Data Mining

The greedy coins game Dynamic Programming

Find if two rectangles overlap

Generic Object Oriented Stack with Template

LeetCode : Word Search

Find an index i such that Arr [i] = i in array of n distinct integers sorted in ascending order.

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

How strtok() Works

Closed Parentheses checker

simple sql injection

Print vertical sum of all the axis in the given binary tree

Stock Buy Sell to Maximize Profit

Maximum size of square sub matrix with all 1’s in a binary matrix

Maximum of all subarrays of size k

Copyright © 2025 · Genesis Framework · WordPress · Log in