Data Structure topics

Diameter of a Binary Tree

In this problem, we are given input as the reference to the root of a binary tree. We need to find the diameter of the tree. We find the diameter using recursion and Depth First Search (DFS).

Algorithms

Algorithm to detect and remove loop in a Linked List

Given a Linked list, find out whether it contains a loop or not. If it does, then remove the loop and make the last node point to NULL.

Problems on Binary Tree

Counting subtrees where nodes sum to a specific value

We will learn about counting the subtrees in a binary tree whose nodes sum to a given value. We will be trying different methods to solve our problem We will solve it in O(N) time complexity and O(H) space complexity where N is number of nodes and H is the height of the tree.

Algorithms

Algorithm to check if a linked list is sorted

In this article, we have explored an algorithm to check if a given Linked List is sorted or not in linear time O(N). It takes constant space O(1).

Algorithms

Check if Linked List is Empty

Checking if the given Linked List is empty depends on the ways Linked List has been formed (with or without root). We have covered both approaches.

Algorithms

Check whether a Singly Linked List is Palindrome or not

Linked List can be palindrome if they have the same order when it traverse from forward as well as backward. This is solved using three methods: using stack, string and by reversing the list.

Algorithms

Transpose Graph

In this article, we will explore the idea of Transpose Graph along with the basics of Graph Data Structures. We have presented an algorithm to get the transpose of a graph as well.

Problems on Binary Tree

Find number of Universal Value subtrees in a Binary Tree

In this article, we will be working on finding number of subtrees whose nodes have same value, called universal value subtree or simply univalue subtree.

Algorithms

Different collision resolution techniques in Hashing

In this article, we have explored the idea of collision in hashing and explored different collision resolution techniques such as open hashing, closed hashing, linear probing, quadratic probing and double hashing.

Problems on Binary Tree

Converting a Sorted Array to Binary Tree

Sorted array is converted to Binary Search Tree for faster search operations and querying. In this article we'll learn to convert any sorted array to binary search tree.

Data Structures

Implementing a Stack using an Array and Linked list

Stack is a linear data structure following LIFO (Last in First out) order and can be implemented using Array or Linked List as an internal data structure.

Data Structures

LogLog (Probabilistic Data Structure for Cardinality)

LogLog is a Probabilistic Data Structure that uses the idea of hashing to compute Cardinality of a given set.

Data Structures

MinHash (Probabilistic Data Structure for Similarity)

MinHash was originally an algorithm to quickly estimate the jaccard similarity between two sets but can be designed as a probabilistic data structure that quickly estimates how similar two sets are.

Data Structures

Probabilistic Data Structures

This is a general overview of probabilistic data structures (with examples of data structures over 5 different categories).

Data Structures

Count Min Sketch

A count min sketch data structure is a probabilistic data structure (a data structure that provides an approximate solution) that keeps track of frequency.

Data Structures

Radix Tree [Compact version of Trie]

radix tree is a compact version of a trie. It takes advantage of this and will store multiple characters / string of text in an edge instead to reduce the number of extra edges and nodes needed.

Data Structures

Two Stack Model / Split Buffer for Text Editors

In two stack model, one stack will represent all the contents left of the cursor while the other stack will represent all the contents right of the cursor. Similar is the idea behind Split buffer.

Data Structures

Data Structures used in Text Editors

A text editor uses a wide range of data structures to implement different features like search, replacing text and much more. These include char buffer, gap buffer, two stack model, doubly linked list and much more.

Algorithms

Reverse a doubly linked list in C++

In this article, we are going to see how to reverse a doubly linked list by reversing the links of each node (without swapping values of nodes) and have implemented the solution using C++.

Algorithms

To check if the linked list is a circular linked list (2 methods)

We will be seeing two efficient methods to determine whether the given linked list is a circular linked list or not. With this, we solve the problem in linear time.

Algorithms

Cycle Detection Algorithms

A cycle in a data structure as we have already seen is a condition with no end. A few popular cycle detection algorithms are Floyd's cycle detection algorithm and Brent’s Cycle Detection Algorithm.

Data Structures

Finding the length of a loop in linked list

In this article, we will look at the method of finding the length of a loop in a linked list. For that you should be able to understand Floyd's loop detection algorithm.

Data Structures

Detect a loop in a linked list (3 methods)

A Loop in a linked list is a condition when a Linked list does not have any end. We have explored different ways to detect loop in a linked list like by marking visited nodes, using hashmap and Floyd's cycle finding algorithm.

Data Structures

Different Self Balancing Binary Trees

A self-balancing binary tree is any tree that automatically keeps its height small in the face of arbitrary insertions and deletions on the tree. We have explored different types like 2 3 tree, Red Black tree, AVL Tree, B Tree, AA Tree, Scapegoat Tree, Splay Tree, Treap and Weight Balanced Tree.

Data Structures

Introduction to 2-3 Trees

A 2-3 Tree is a tree data structure where every node with children has either two children and one data element or three children and two data elements. A node with 2 children is called a 2-NODE and a node with 3 children is called a 3-NODE.