Introduction: Google search has a feature called automatic search completion. When you start typing a search query, google will try to auto complete your sentence. An example is shown below: Google binary seal binary search binary search tree binary search java binary search tree java Press Enter to search. a This project will simulate the same functionality of search completion using C++ and command line. Implementation: A simple search completion can be implemented using a Trię data structure. A Trie is similar to a tree but it can hold more information about data. For detailed explanation of Trie data structure, please see: https://en.wikipedia.org/wiki/Trie The way we implement the search completion is to use the edge to denote letters in a valid search query and use the node as the resulting complete search string. An example of adding word Top to our Trie is shown below. top op р 16 ten inn I 16 First, starting at the root node we find the edge "t". So we remove "t" from original string and move to the node "t" pointed by edge "t". From the t node we find letter "o", so we remove "o" from original string and move to the node "to" pointed by edge "o". Then we cannot find edge "p", so we add edge "p" to node "to" and point edge "p" to node "top". Notice some nodes are denoted by a number. For example, the node tea is denoted by number 3. These node indicate that the string contained in the node is a valid search query. For example, node "te" is not a valid search query while "tea", "ted" and "ten" are. Another example is "", "in", and "inn" are all valid 1 search queries. In this project you can use a single Boolean value to indicate whether a node contains a valid search query or not. To auto complete a query with an existing Trie, you use the depth first traversal on Trie. For example, if I started typing letter "t", then you will start depth first search on the subtree of node "t". After you complete your depth first search, you should return search query string "to", "top", "tea", "ted" and "ten" as possible auto completion options. Project Details: This project will be two parts. Part I is to construct a Trię using a dictionary file provided. Part II is to implement a command-line search auto complete interface. Part I: Part I: Dictionary.txt is provided to you to construct the Trie. Each line contains a valid search query. Your task is to insert these queries into your Itie Part II: Using the Trie class completed in Part I, create a C++ program that takes an user input and output auto completion options. The interface should be similar to the following: $>Please type search queries: $> binary sea $>Your options are: $> binary search Sbinary search tree $> binary search tree java Implement the search.cpp file, which contains an empty main function. Implement the main() function and add other necessary functions to search.cpp to complete part II Introduction: Google search has a feature called automatic search completion. When you start typing a search query, google will try to auto complete your sentence. An example is shown below: Google binary seal binary search binary search tree binary search java binary search tree java Press Enter to search. a This project will simulate the same functionality of search completion using C++ and command line. Implementation: A simple search completion can be implemented using a Trię data structure. A Trie is similar to a tree but it can hold more information about data. For detailed explanation of Trie data structure, please see: https://en.wikipedia.org/wiki/Trie The way we implement the search completion is to use the edge to denote letters in a valid search query and use the node as the resulting complete search string. An example of adding word Top to our Trie is shown below. top op р 16 ten inn I 16 First, starting at the root node we find the edge "t". So we remove "t" from original string and move to the node "t" pointed by edge "t". From the t node we find letter "o", so we remove "o" from original string and move to the node "to" pointed by edge "o". Then we cannot find edge "p", so we add edge "p" to node "to" and point edge "p" to node "top". Notice some nodes are denoted by a number. For example, the node tea is denoted by number 3. These node indicate that the string contained in the node is a valid search query. For example, node "te" is not a valid search query while "tea", "ted" and "ten" are. Another example is "", "in", and "inn" are all valid 1 search queries. In this project you can use a single Boolean value to indicate whether a node contains a valid search query or not. To auto complete a query with an existing Trie, you use the depth first traversal on Trie. For example, if I started typing letter "t", then you will start depth first search on the subtree of node "t". After you complete your depth first search, you should return search query string "to", "top", "tea", "ted" and "ten" as possible auto completion options. Project Details: This project will be two parts. Part I is to construct a Trię using a dictionary file provided. Part II is to implement a command-line search auto complete interface. Part I: Part I: Dictionary.txt is provided to you to construct the Trie. Each line contains a valid search query. Your task is to insert these queries into your Itie Part II: Using the Trie class completed in Part I, create a C++ program that takes an user input and output auto completion options. The interface should be similar to the following: $>Please type search queries: $> binary sea $>Your options are: $> binary search Sbinary search tree $> binary search tree java Implement the search.cpp file, which contains an empty main function. Implement the main() function and add other necessary functions to search.cpp to complete part II