Data Structures

This category contains all the posts related to data structures. For e.g.: Hash Tables, Linked Lists, Trees, Graphs, Heaps, Tries etc..

Build Balanced Binary Search Tree from Array

Introduction This post describes the algorithm to build binary search tree from array of sorted elements. However, this technique can be used to build balanced binary search tree from array. A balanced binary tree is a binary tree which has minimum height. To know more about various aspects of a binary search tree, please visit my previous posts. What does balanced means? In this post as we are trying to build a BST, we will assume the input to be a sorted array. In case, we are just building a binary tree, we can take any array as an input. Let me explain the process with the help of a ...
Read More

Fastest Reach in Snakes and Ladders

Introduction For those who are not familiar with the snakes and ladders game. Here is a link for introduction. So the fastest reach in snakes and ladders, is a modified version of the game. So, you are playing the game called snakes and ladders and you have an enchanted dice. You are the master of the dice and you can command it to get any number between 1 and 6 both inclusive. This means that when you throw the dice, the number on the upper face is totally controlled by you. If you ask for a 5, you get a 5 and so on. Problem Statement - Fastest Reach in Snakes and Ladders The problem in ha...
Read More

Single Source Shortest Path For Undirected Graph

Introduction Single source shortest path for undirected graph is basically the breadth first traversal of the graph. Here the graph we consider is unweighted and hence the shortest path would be the number of edges it takes to go from source to destination. You can find posts on the same topic for weighted graphs, and that is solved using Dijkstra's or Bellman Ford algorithms. This post is written from the competitive programming perspective. Here I want to focus on the details of simplified implementations. Problem Statement - Shortest Path for Undirected Graph Most of the times, the probl...
Read More

Removing Duplicates from Sorted Linked List

Problem Statement You are given a singly sorted linked list, which has repeated elements. The task at hand is to remove the duplicates from the linked list. Here is a diagram to explain the problem statement Solution for Removing Duplicates from Sorted Linked List As the linked list is sorted, if two nodes contain duplicates, they will always be adjacent to each other. Hence, the trick is to Maintain two pointers (Current_Node_Ptr and Next_Node_Ptr). If the Next_Node_Ptr points to a duplicate node, delete the node and advance the Next_Node_Ptr Make the next of Current_No...
Read More

Splitting and Merging B Tree Nodes

This post is to be read in conjunction with another post Introduction to B Trees. Here we learn that in certain operations the B Tree properties might get disturbed and it will need a fix. Splitting and Merging B Tree Nodes are the only operations which can re-establish the properties of the B Tree. How does a B Tree get unbalanced? The tree is not just to read and search data. There are operations which update the tree either by deleting a key, inserting a new key or just updating the values stored against the key. The Insert and Delete operations tend to modify the structure of the tree...
Read More