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.
Suffix trees are a compressed version of the trie that includes all of a string's suffixes. Suffix trees can be used to solve many string problems that occur in text-editing, free-text search, etc. The ability to search efficiently with mismatches might be considered their greatest strength.
AVL Trees named after its inventors Adelson-Velsky and Landis, is a unique variation of the Binary Search Tree, which is a self-balancing BST. The property of AVL Trees is that they automatically attain the tree's minimum possible height after executing any operation.
Dynamic Programming is a popular problem-solving approach in data structures and algorithms, where we solve problems by combining the solutions to subproblems like the divide-and-conquer method. But rather than computing the same sub-problem repeatedly, we solve the sub-problem once and store the calculated value in extra memory to avoid the recomputation.
Trie is a famous data structure used to store and process data, especially strings. It is a tree where each node represents a prefix or end of a word (the path traced from the root to that node). The word trie comes from retrieval as a trie can retrieve all the words with a given prefix.
There are two ways to solve and implement dynamic programming problems: 1) The top-down approach (Memoization) and 2) The bottom-up approach (Tabulation). Both approaches perform similarly in one way: They use extra memory to store the solution to sub-problems, avoid the recomputation and improve the performance by a huge margin. On another side, both of them are different in so many ways, and understanding this difference would help us to make critical decisions during problem-solving.
Divide and conquer and dynamic programming are popular problem-solving approaches in data structure and algorithms. Both approaches look similar in one way: They use a similar idea to break problems into subproblems and combine their solutions to obtain the solution to the original problem. But there are a lot of differences between both approaches.
There could be various patterns of dynamic programming problems. In practice, there are two popular categories of problems that can be solved using dynamic programming: 1) Optimization problems and 2) Counting problems.
Trees can have any number of children, but the simplest and most common type of tree is a binary tree, where each node has at most two child nodes (called left child and right child). In other words, a node in a binary tree can have 0 or 1 or 2 child nodes.
Divide and conquer is a recursive problem-solving approach that divides the problem into smaller subproblems, recursively solves the subproblems, and combines the solutions to the subproblems to get the solution of the original problem.
In this blog, we will learn how to use segment trees for efficient point and range updates. For the point update query, update(idx, val), we need to increment the element at the index idx from the original array by val, i.e. arr[idx] = arr[idx] + val. For the range update query, update(l, r, val), we must increment all the elements from index l to r from the original array by val.
This blog highlights some popular problem-solving strategies for solving problems in DSA. Learning to apply these strategies could be one of the best milestones for the learners in mastering data structure and algorithms. Later we will write a separate blog on each problem-solving approach. Enjoy learning, Enjoy algorithms!
Algorithmic thinking is a method for solving data structure and algorithms problems based on a clear definition of the steps logically and repeatedly. The best idea would be to develop this skill independently from learning programming with proper practice and visualisation. This could help us learn several problem-solving strategies in coding.
Iterative and Recursive approaches are important for solving data structures and algorithms problems. An iterative approach is about repeatedly executing some code statements using a loop, and a recursive method involves solving the problem using the smaller sub-problems.
Recursion means solving the problem via the solution of the smaller sub-problem. This blog will answer some critical questions like - what is recursion? What are its advantages and disadvantages? How do you identify recursion problems? What is the difference between recursion and iteration? etc.
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. Explore this blog to learn how hash tables work in programming?
A heap is a complete binary tree structure where each element satisfies a heap property. We learn two types of the heap in programming: 1) max-heap, which satisfies the max heap property, and 2) min-heap, which satisfies the min-heap property. We use the heap to implement the priority queue efficiently.
The counting sort algorithm assumes that each n input element is an integer in the range 0 to k. So by using array indexing as a tool for determining relative order, counting sort can sort n numbers in O(k + n) time when k = O(n). In other words, counting sort is one of the popular linear time sorting algorithms that works in O(n) time complexity if input elements are an integer in the range 0 to k.
A Segment Tree is a data structure used to answer multiple range queries on an array efficiently. Also, it allows us to modify the array by replacing an element or an entire range of elements in logarithmic time. This blog will focus on the build and query operations on segment trees.
These are some critical reasons to study sorting algorithms: 1) It can help us to learn analysis of algorithms and various problem-solving approaches 2) Sorting can work as a problem-solving approach to solve several coding problems 3) We can learn code optimization techniques and variations in boundary conditions using sorting.
Comparison-based sorting algorithms like merge sort, quicksort, insertion sort, heap sort, etc., determine the sorted order based on the comparisons between the input elements. We call such algorithms comparison sort. The critical question is: Why is the lower bound of comparison sort O(nlogn)? Explore this blog to get an answer!
To process data stored in a binary tree, we need to traverse each tree node, and the process to visit all nodes is called binary tree traversal. In this blog, we will be discussing three popular recursive tree traversals: preorder, inorder and postorder traversals. These traversals are also called depth-first search traversal or dfs traversal in data structures.
We cannot adjust the size of regular arrays in the middle of the code execution. We solve this problem using the dynamic array, where we can increase the array size dynamically as we need them. The Vector class in C++ and ArrayList in Java class use a dynamic array for storing the elements.
The code structure of a well-designed algorithm using data structure is just like a good house design. So learning algorithms require a good understanding of data structures properties, implementation techniques, and efficiency of critical operations. The fact is: Data Structures are the core building blocks of algorithms and real-life applications.
A Fenwick tree is a data structure that efficiently updates elements and calculates prefix sums in an array. It takes O(logn) time for both updates and range sum queries. It is also called Binary Indexed Tree (BIT), which was first described in the paper titled “A new data structure for cumulative frequency tables” (Peter M. Fenwick, 1994).
An array is a contiguous block of memory of the same type of elements where the size is equal to the number of elements in that array, which must be fixed. It is a structure of data such that each element can be efficiently located by its index or memory address.
Comparison of sorting algorithms based on different parameters helps us choose an effcient sorting method in various problem-solving scenarios. You will get an answer to the following questions: how to compare two sorting algorithms? Which sorting is best in terms of properties like efficiency, in-place, stability, online vs. offline, etc.
In recursive DFS traversals of a binary tree, we have three basic elements to traverse— root, left subtree, and right subtree. The traversal order depends on the order in which we process the root node. Here recursive code is simple and easy to visualize — only one function parameter and 3–4 lines of code. So critical question would be — How can we convert it into iterative code using stack? To simulate the recursive traversal into an iterative traversal, we need to understand the flow of recursive calls.
Level order traversal accesses nodes in level by level order. This is also called breadth-first search traversal or BFS traversal. Here we start from the root node and process it, then process all the nodes at the first level, then process all the nodes at the second level, and so on. In other words, we explore all nodes at the current level before moving on to the nodes at the next level.
Explore this blog to answer these questions related to complexity analysis: why time complexity analysis is important? What are the criteria to define the complexity of an algorithm? How do we analyze the time complexity of an algorithm? How do we represent algorithm time complexity in the form of big O notation?
Learning analysis of recursion is critical to understand the time complexity analysis of recursive algorithms. We will discuss these concepts related to the recursion analysis: Recurrence relations of recursive algorithms, steps to analyze the time complexity of recursion, Recursion tree method, and master theorem to analyze divide and conquer algorithms.
There are several loop patterns in programming like a loop running constant time, a loop running n times, a loop growing exponentially, a loop running based on the specific condition, consecutive single loops, two nested loops, three nested loops, consecutive single loop with nested loops, etc. So for designing a better algorithm or optimizing the code, we should learn to analyze the time complexity of the loop in terms of Big-O notation.
Sorting algorithms are the most fundamental problems to study in data structure and algorithms. But the critical question is - why we learn the design, code, and analysis of the sorting algorithms? Explore and Think!
Iteration is a process to repeat a sequence of code instructions a specified number of times or until a specific condition is met. It helps us to solve several coding problems in data structure and algorithms. We implement iteration using the two most common types of loops in programming languages: the while loop and the for loop.
A comprehensive guide to master data structures and algorithms and crack the coding interview. This could help programmers prepare a step-by-step learning plan for the coding interview preparation. Explore and Enjoy!
The concept of algorithm is essential for building high-performance software applications and cracking the coding interview to get a high-paying job in the software industry. So learning data structure and algorithms is one of the important career skills for programmers. Definition of the algorithm: An algorithm is a step-by-step procedure to transform a given input to the desired output and solve a computational problem.
There can be four reasons to learn data structures and algorithms: 1) An algorithm is a technology in itself! 2) It is at the core of library functions and APIs 3) It is important for cracking the coding interview 4) Algorithms are beautiful! This blog will help you develop a long-term motivation for learning DSA.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.