Trie data structure has many useful applications, one of the important applications of the trie is auto-suggestion when user inputs using the keyboard. Let us assume we have a dictionary that contains “APPLE”, “APE”, “GOD”, “GOOD”, “GUN”. So, when a user enters “GO” then our auto-suggestion suggests “GOD”, “GOOD” as a suggested list of words.Read More »
Trie data structures are useful to process and search in large character data sets. It takes only orders of word length to search a word in length file or a million words dictionary. Some examples where Trie’s use. In finding words in large files. In finding any word in the large dictionary of words. InRead More »
Given a sorted array that contains both negative and positive integers we aim to get its squares array in sorted orders. Let us understand this with an example. Let’s understand how we can solve this problem in linear time. To solve this in linear time, we have to take two handles which represent the startRead More »
Given a Binary Search Tree (BST) contains integers and an integer. We aim to find the nearest node to input integer in the BST. Let us understand this with an example. Let’s see how our solution works to get the nearest node to the target integer. This algorithm runs with O(H), where is ‘H’ isRead More »
Given a graph with an adjacency list, we aim to clone the complete graph with edges. Cloning does creates a new memory for similar data. Let us understand this with a three-node example graph. We can solve this problem using either DFS or BFS. Let’s solve this problem using DFS. Our Graph object contains theRead More »
Given a set of parentheses (a string expression), we aim to validate those parentheses. Let us see this with some examples. We can solve this problem using stack data structure. Here we have taken three sets of braces which are ‘{}’, ‘()’ and ‘[]’. Algorithm Check if stack not empty and current bracket character isRead More »
We were given a binary search tree(BST) and a sum. We aim to find any two nodes with a total that is equivalent to input sum. Let us see this with an example. In the above BST, we are going to find a sum of two nodes as 9. Our approach to solve this, firstlyRead More »
A stack is a LIFO(Last In First Out) data structure. Like all other data structures, it supports two basic operations like push(insert), pop(delete), with constant complexity (i.e., O(1)). In contrast, usually, the stack doesn’t have a min (minimum) as a default operation. To have this min operation, we need to have an auxiliary stack (whichRead More »
Heap is physically an array-like storage data structure whereas virtually we can see this as a binary tree. In heap data structure the element in the 0th index represents as the root of the tree and its children indices are calculated using the below formula. Example of Heap Let’s take a heap example that hasRead More »
Let us take two linked lists which at some point merge as one list. Our goal is to find the point where the given two linked lists merging. The most optimized solution for this problem is to find the maximum length list and jump each node until both lists length becomes the same. Below isRead More »
Graphs are most commonly using a data structure in computer applications, networks, and maps. These are introduced in early computing days. By definition a graph with “V” vertices (nodes) and “E” edges, where each edge “e” associates with one or more vertices. A graph with nodes {A, B, C, D, E} and edges {e1, e2,Read More »
A binary search tree is a binary tree, with the content of all elements in the left subtree of a node are lesser than the content in the parent. Whereas all nodes content in its right subtree are greater than its parent. Let’s see below two example binary search trees. As observed in the aboveRead More »
A binary tree is a tree data structure with a maximum of two children in each node. Similarly, the recursive meaning of a binary tree is a tree (L, P, R) where L and R are binary trees with P as root. A binary tree node has pointed to at most another two nodes. ARead More »
Queues are data structures on which operations are done in the first-in-first-out(FIFO) order. Unlike stacks, queues are open at both ends. For example lets take a simple queue of people who are standing to enter into an exhibition. There are two types of queues, those are Linear Queues and Circular Queues. Below is a linearRead More »
Stack is the most popular and historical data structure. A list of items arranged one on top of others. Stack data structure popularly used to maintain program memory stack. It follows the last-in-first-out order. Let’s consider a stack of discs as shown in the below picture. As shown in this diagram, only the top nodeRead More »