The most used but overlooked data structure | Learn Data Structure with Shubham part 4

 TRIE 

Trie data structure 

    or (radix tree(radix trie is compressed trie), prefix tree, digital tree)

        

A trie, also called digital tree or prefix tree, is a kind of search tree—an ordered tree data structure used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated; i.e., the value of the key is distributed across the structure

            

Advantages:

1. Sometimes Space-Efficient. If you're storing lots of words that start with similar patterns, tries may reduce the overall storage cost by storing shared prefixes once.

            

2. Efficient Prefix Queries. Tries can quickly answer queries about words with shared prefixes, like:

How many words start with "choco"?

What's the most likely next letter in a word that starts with "strawber"?    

Disadvantages:

1. Usually Space-Inefficient. Tries rarely save space when compared to storing strings in a set.

ASCII characters in a string are one byte each. Each link between trie nodes is a pointer to an address—eight bytes on a 64-bit system. So, the overhead of linking nodes together often outweighs the savings from storing fewer characters.

2. Not Standard. Most languages don't come with a built-in trie implementation. You'll need to implement one yourself.

Applications:

1. Dictionary

2. Spell checker applications

3. Autocomplete

Suffix trie: 

Will Post in another Post

Trie vs BST: 

Will post in another Post

Trie vs Hashing: 

Will Post in another Post

srcs and refs: 

• https://www.interviewcake.com/concept/java/trie       
• https://medium.com/basecs/trying-to-understand-tries-3ec6bede0014
• https://www.hackerearth.com/practice/data-structures/advanced-data-structures/trie-keyword-tree/tutorial/
• https://www.geeksforgeeks.org/advanced-data-structures/#Trie
• https://en.wikipedia.org/wiki/Trie     

BFS and DFS | Learn Data Structure with Shubham part 3

Let us tackle with the fear of BFS and DFS.

While both BFS and DFS are algorithms for traversing or searching tree or graph data structures. Let us dive into more details about their implementation, applications and time complexity.

BFS

Input Graph: 

Output in BFS: ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"]

What is BFS: 

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'), and explores all of the neighbour nodes at the present depth prior to moving on to the nodes at the next depth level.

 

Implementation for BFS:

Time Complexity of BFS:

The time complexity can be expressed as O(|V|+|E|), since every vertex and every edge will be explored in the worst case. |V| is the number of vertices and |E| is the number of edges in the graph. Note that O(|E|) may vary between O(1) and O(|V|^{2}), depending on how sparse the input graph is.

When the number of vertices in the graph is known ahead of time, and additional data structures are used to determine which vertices have already been added to the queue, the space complexity can be expressed as O(|V|), where |V| is the number of vertices. This is in addition to the space required for the graph itself, which may vary depending on the graph representation used by an implementation of the algorithm.

Why and where BFS is used:

1) Shortest Path and Minimum Spanning Tree for unweighted graph In an unweighted graph, the shortest path is the path with least number of edges. With Breadth First, we always reach a vertex from given source using the minimum number of edges. Also, in case of unweighted graphs, any spanning tree is Minimum Spanning Tree and we can use either Depth or Breadth first traversal for finding a spanning tree.

2) Peer to Peer Networks. In Peer to Peer Networks like Torrent, Breadth First Search is used to find all neighbour nodes.

3) Crawlers in Search Engines: Crawlers build index using Breadth First. The idea is to start from source page and follow all links from source and keep doing same. Depth First Traversal can also be used for crawlers, but the advantage with Breadth First Traversal is, depth or levels of the built tree can be limited.

4) Social Networking Websites: In social networks, we can find people within a given distance ‘k’ from a person using Breadth First Search till ‘k’ levels.

DFS

Input Graph: 

Output in DFS: ["A", "B", "E", "F", "I", "J", "C", "D", "G", "K", "H"]

Why and where DFS is used?

1) For a weighted graph, DFS traversal of the graph produces the minimum spanning tree and all pair shortest path tree.

2) Detecting cycle in a graph
A graph has cycle if and only if we see a back edge during DFS. So we can run DFS for the graph and check for back edges.

3) Path Finding
We can specialise the DFS algorithm to find a path between two given vertices u and z.
i) Call DFS(G, u) with u as the start vertex.
ii) Use a stack S to keep track of the path between the start vertex and the current vertex.
iii) As soon as destination vertex z is encountered, return the path as the
contents of the stack

Srcs:

• https://en.wikipedia.org/wiki/Breadth-first_search
• https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/
• https://www.geeksforgeeks.org/applications-of-breadth-first-traversal/
• https://www.geeksforgeeks.org/applications-of-depth-first-search/
• https://www.youtube.com/watch?v=zaBhtODEL0w
• https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/tutorial/