# Longest Common Prefix using Trie

Given a set of strings, find the longest common prefix.

```Input  : {“geeksforgeeks”, “geeks”, “geek”, “geezer”}
Output : "gee"

Input  : {"apple", "ape", "april"}
Output : "ap"
```

Previous Approaches : Word by Word Matching , Character by Character Matching, Divide and Conquer , Binary Search.

Steps:

• Insert all the words one by one in the trie. After inserting we perform a walk on the trie.
• In this walk, go deeper until we find a node having more than 1 children(branching occurs) or 0 children (one of the string gets exhausted).

This is because the characters (nodes in trie) which are present in the longest common prefix must be the single child of its parent, i.e- there should not be branching in any of these nodes.

Algorithm Illustration considering strings as – “geeksforgeeks”, “geeks”, “geek”, “geezer” ## C++

 `// A Program to find the longest common ` `// prefix of the given words ` ` `  `#include ` `using` `namespace` `std; ` ` `  `// 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 ` `struct` `TrieNode ` `{ ` `    ``struct` `TrieNode *children[ALPHABET_SIZE]; ` ` `  `    ``// isLeaf is true if the node represents ` `    ``// end of a word ` `    ``bool` `isLeaf; ` `}; ` ` `  `// Returns new trie node (initialized to NULLs) ` `struct` `TrieNode *getNode(``void``) ` `{ ` `    ``struct` `TrieNode *pNode = ``new` `TrieNode; ` ` `  `    ``if` `(pNode) ` `    ``{ ` `        ``int` `i; ` ` `  `        ``pNode->isLeaf = ``false``; ` ` `  `        ``for` `(i = 0; i < ALPHABET_SIZE; i++) ` `            ``pNode->children[i] = NULL; ` `    ``} ` ` `  `    ``return` `pNode; ` `} ` ` `  `// If not present, inserts the key into the trie ` `// If the key is a prefix of trie node, just marks leaf node ` `void` `insert(``struct` `TrieNode *root, string key) ` `{ ` `    ``int` `length = key.length(); ` `    ``int` `index; ` ` `  `    ``struct` `TrieNode *pCrawl = root; ` ` `  `    ``for` `(``int` `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->isLeaf = ``true``; ` `} ` ` `  `// Counts and returns the number of children of the ` `// current node ` `int` `countChildren(``struct` `TrieNode *node, ``int` `*index) ` `{ ` `    ``int` `count = 0; ` `    ``for` `(``int` `i=0; ichildren[i] != NULL) ` `        ``{ ` `            ``count++; ` `            ``*index = i; ` `        ``} ` `    ``} ` `    ``return` `(count); ` `} ` ` `  `// Perform a walk on the trie and return the ` `// longest common prefix string ` `string walkTrie(``struct` `TrieNode *root) ` `{ ` `    ``struct` `TrieNode *pCrawl = root; ` `    ``int` `index; ` `    ``string prefix; ` ` `  `    ``while` `(countChildren(pCrawl, &index) == 1 && ` `            ``pCrawl->isLeaf == ``false``) ` `    ``{ ` `        ``pCrawl = pCrawl->children[index]; ` `        ``prefix.push_back(``'a'``+index); ` `    ``} ` `    ``return` `(prefix); ` `} ` ` `  `// A Function to construct trie ` `void` `constructTrie(string arr[], ``int` `n, ``struct` `TrieNode *root) ` `{ ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``insert (root, arr[i]); ` `    ``return``; ` `} ` ` `  `// A Function that returns the longest common prefix ` `// from the array of strings ` `string commonPrefix(string arr[], ``int` `n) ` `{ ` `    ``struct` `TrieNode *root = getNode(); ` `    ``constructTrie(arr, n, root); ` ` `  `    ``// Perform a walk on the trie ` `    ``return` `walkTrie(root); ` `} ` ` `  `// Driver program to test above function ` `int` `main() ` `{ ` `    ``string arr[] = {``"geeksforgeeks"``, ``"geeks"``, ` `                    ``"geek"``, ``"geezer"``}; ` `    ``int` `n = ``sizeof` `(arr) / ``sizeof` `(arr); ` ` `  `    ``string ans = commonPrefix(arr, n); ` ` `  `    ``if` `(ans.length()) ` `        ``cout << ``"The longest common prefix is "` `             ``<< ans; ` `    ``else` `        ``cout << ``"There is no common prefix"``; ` `    ``return` `(0); ` `} `

## Java

 `// Java Program to find the longest common ` `// prefix of the given words ` `public` `class` `Longest_common_prefix { ` `     `  `    ``// Alphabet size (# of symbols) ` `    ``static` `final` `int` `ALPHABET_SIZE = ``26``; ` `      `  `    ``// Trie node ` `    ``static` `class` `TrieNode ` `    ``{ ` `        ``TrieNode[] children = ``new` `TrieNode[ALPHABET_SIZE]; ` `      `  `        ``// isLeaf is true if the node represents ` `        ``// end of a word ` `        ``boolean` `isLeaf; ` `         `  `        ``// constructor ` `        ``public` `TrieNode() { ` `            ``isLeaf = ``false``; ` `            ``for` `(``int` `i = ``0``; i < ALPHABET_SIZE; i++) ` `                ``children[i] = ``null``; ` `        ``} ` `    ``}; ` `      `  `    ``static` `TrieNode root; ` `    ``static` `int` `indexs; ` `      `  `    ``// If not present, inserts the key into the trie ` `    ``// If the key is a prefix of trie node, just marks ` `    ``// leaf node ` `    ``static` `void` `insert(String key) ` `    ``{ ` `        ``int` `length = key.length(); ` `        ``int` `index; ` `      `  `        ``TrieNode pCrawl = root; ` `      `  `        ``for` `(``int` `level = ``0``; level < length; level++) ` `        ``{ ` `            ``index = key.charAt(level) - ``'a'``; ` `            ``if` `(pCrawl.children[index] == ``null``) ` `                ``pCrawl.children[index] = ``new` `TrieNode(); ` `      `  `            ``pCrawl = pCrawl.children[index]; ` `        ``} ` `      `  `        ``// mark last node as leaf ` `        ``pCrawl.isLeaf = ``true``; ` `    ``} ` `      `  `    ``// Counts and returns the number of children of the ` `    ``// current node ` `    ``static` `int` `countChildren(TrieNode node) ` `    ``{ ` `        ``int` `count = ``0``; ` `        ``for` `(``int` `i=``0``; i

Output :

`The longest common prefix is gee`

Time Complexity : Inserting all the words in the trie takes O(MN) time and performing a walk on the trie takes O(M) time, where-

```N = Number of strings
M = Length of the largest string
```

Auxiliary Space: To store all the strings we need to allocate O(26*M*N) ~ O(MN) space for the Trie.