Tries and Suffix

What is a Tree?

A tree is a Data Structure which is arranged in the form of multiple nodes holding some data, connected to each other as in the figure below. The node at the top is called the root. All the nodes reachable from it, below it, are it's children, and the node connected to it, directly above it, i.e. on the path to the root is it's parent.

A Tree

Time and Space Complexity

• Time complexity of an algorithm gives the measure of time taken by it to run as a function of the length of the input. Similarly, Space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input.
• Recall that if our word list (the one we are searching through) is an array of length N, and our algorithm iterates through the array once, then time complexity will be O(N). If for each element we have to perform m operations, where m is the length of the word, then the algorithm is O(NM).