data-structures

Level order traversal accesses nodes in level by level order. This is also called breadth first search or BFS traversal. Here we start processing from the root node, then process all nodes at the first level, then process all nodes at the second level, and so on. In other words, we explore all nodes at the current level before going to nodes at the next level.

Design and implement a stack that supports the push, pop, top, and retrieval of the minimum element in constant time. In other words, our goal is to implement the MinStack class, which supports push, pop, top, and getMin operations with O(1) time complexity. Note: The pop, top, and getMin operations will always be called on non-empty stacks.

We can easily implement recursive binary tree traversals (preorder, inorder, and postorder) iteratively using a stack. We need to understand the flow of recursive calls in DFS traversal and mimic what the compiler does in the background. So, we need to follow a similar process and use our own stack to simulate the recursive binary tree traversal using iteration or without using recursion.

Stack helps us in easy access and removal of the most recently added element. So there are several applications of the stack in data structures and algorithms. Some popular applications are: 1) Back and forward buttons in the browser 2) UNDO/REDO functionality in text editors 3) Memory management 4) Delimiter checking 5) Implementing recursion 6) Expression conversion and evaluation, etc.

The stack data structure is a type of collection that follows the Last In, First Out (LIFO) principle, meaning that the last item added to the stack will be the first one to be removed.Stack is a linear data structure that supports two primary operations: push and pop. When we add an element to the top, it is called a push operation. When we remove an element from the top, it is called a pop operation.

A Fenwick tree, also known as a binary indexed tree (BIT), is a data structure that allows for efficient updates and prefix sum calculations on an array. It has a time complexity of O(logn) for both updates and range sum queries. Fenwick trees were first described in a 1994 paper by Peter M. Fenwick titled "A new data structure for cumulative frequency tables.

Given the head of a linked list, write a program to find if linked list has a cycle or not. Return true if there is a cycle or loop in the linked list. Otherwise, return false. A linked list with cycle causes iteration to fail because the iteration will never reach the end. So, detecting a linked list loop is important before applying an iterative approach.

Write a program to implement a stack using queues. We must use queue operations like enqueue, dequeue, front, size to implement stack operations like push, pop, and top. We have discussed three approaches: 1) Using two queues: O(n) pop and O(1) push 2) Using two queues: O(1) pop and O(n) push 3) Using one queue: O(1) pop and O(n) push.

Write a program to implement queue using stack. We should use stack operations like push, pop, top, size, and isEmpty for implementing queue operations like enqueue, dequeue, and front. In this blog, we have discussed two approaches for implementing queue using two stacks: 1) Dequeue O(1) and Enqueue O(n) 2) Enqueue O(1) and Dequeue O(1).

A head pointer of a singly linked list is given, write a program to reverse linked list and return the head pointer of the reversed list. We need to reverse the list by changing the links between nodes. Note: This is an excellent question to learn problem-solving using both iteration (Three-pointers) and recursion (Decrease and conquer approach).

There are three types of recursive tree traversals: preorder, inorder and postorder. This classification is based on the visit sequence of root node 1) Preorder traversal: root is visited first 2) Inorder traversal: root is visited after left subtree 3) Postorder traversal: root is visited last. These are also called depth first search or DFS traversal.

AVL Trees is a height-balanced BST named after its inventors, Adelson-Velsky and Landis. This is a variation of binary search trees, also known as self-balancing BST. The property of AVL Trees: The absolute difference of height between left and right subtree is at max 1, which could help us to perform bst operations in O(logn) time complexity.

The least recently used (LRU) cache is one of the popular caching strategies, which defines the policy to discard the least recently used items first from the cache and make room for new elements when the cache is full. It is used to organize items in order of their use, which allows identifying items that have not been used for a long time.

The least frequently used (LFU) is a cache algorithm used to manage memory within a computer. In this method, the system keeps track of the number of times a block is referenced in memory, and when the cache is full, our system removes the item with the lowest reference frequency. LFU cache get and put operation works in O(1) average time complexity.

Bloom filter is a space-efficient data structure that tells whether an element may be in a set (either a false positive or true positive) or definitely not present in a set (True negative). It will take O(1) space, regardless of the number of items inserted. However, their accuracy decreases as more elements are added.

Hashing is a technique to map (key, value) pairs into the hash table using a hash function. It uses an array of size proportional to the number of keys and calculates an array index from the key using a hash function. We use hashing/hash tables in several real life applications and solve various coding questions efficiently in data structures.

Heap is a complete binary tree structure where each node satisfies a heap property. We learn two types of heap data structure: 1) Max heap, which satisfies the max heap property, and 2) Min heap, which satisfies the min-heap property. We use heap data structures to implement priority queues and solve several coding problems efficiently.

Binary search tree (BST) is a sorted binary tree, where key stored in each node must satisfy the binary search tree property: 1) Keys in the left subtree ≤ Node key 2) Keys in the right subtree ≥ Node key 3) Both subtrees must be binary search trees. In this blog, we have discussed the key properties, operations and differences of BST with a hash table.

The root of the binary search tree and a key k is given. Write a program to insert key k into the binary search tree. Note: BST structure will change after the insertion. So we need to perform insertion in such a way that the BST property continues to hold. In this blog, we have discussed recursive and iterative implementations of insertion in BST.

A well-designed code using data structure is just like a design of a good house. So mastering algorithms require a good understanding of data structure definition, classification, types, implementation techniques, key operations, etc. We should also explore various real-life applications to understand the use case of data structures.

We know that a binary tree is a rooted tree in which each node has no more than two children. We can extend this definition to an n-ary tree. If a tree is rooted in which each node has no more than n children, it is called an n-ary tree. In other words, n ary trees are tree data structures with up to n children nodes for each node present in the tree.

Suffix trees are a compressed version of the trie that includes all of a string's suffixes. It can be used to solve many string problems that occur in text editing, free-text searches, etc. Some popular applications of suffix trees are string search, finding the longest repeated substring, finding the longest common substring, data compression, etc.

In python, sets and dictionaries are unordered data structures frequently used in machine learning applications. In this blog, we have explained these concepts: 1) What is set in python? 2) Important operations on sets, 3) Conversion of lists into sets 4) What is dictionary in python? 5) Operations on dictionaries? 6) Comparison of sets and dictionaries.

Tuples and lists are two most popular python data structures used in Machine Learning and Data Science applications. They are also called compound data types because they can store a mixture of primitive data types like strings, ints, and floats. Tuples are static and immutable while lists are dynamic and mutable, but tuples are memory efficient as compared to lists. We will explore these data structures in detail in this blog.

We mainly use trie data structure to process strings efficiently. It is a tree where each node represents a prefix or end of a word. The best thing is that the time complexity of trie operations depends on string length, which is independent of number of strings. Applications of trie: Autocomplete search, longest prefix matching, spell checker, etc.

In this blog, we will learn how to use segment trees for efficient point and range updates. For point update query, update(idx, val), we need to increment element at index idx from the original array by val, i.e. arr[idx] = arr[idx] + val. For range update query, update(l, r, val), we increment all elements from index l to r from the original array by val.

A segment tree is a binary tree data structure such that each node stores information about a range. We use segment trees to efficiently answer multiple range queries on an array like range minimum, range maximum, range sum, etc. Also, it allows us to modify the array by replacing an element or an entire range of elements in logarithmic time.

A dynamic array is a variable-size data structure which increases array size dynamically as we need them. Dynamic arrays overcome a limitation of static arrays, where we cannot adjust the size in the middle of the code execution. It is implemented as a standard library in programming languages like vector in C++ and ArrayList in Java.

An array is a sequential collection of elements of same data type and stores data elements in a continuous memory location. Each element can be efficiently located by its index, which can be easily calculated by adding an offset to the base address. This blog has discussed various array concepts like array types, operations, properties, etc.