Find shortest path using Dijkstra's Algorithm

 Posted on July 30, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

The Dijkstra’s algorithm entails the following procedure: - The breadth-first approach is used to traversal the network, however the difference here is instead of a queue data structure to store the traversed vertex this algorithm uses a priority queue. The priority queue helps to remove the items in order of values rather than in order of being added to the queue. - Have an account of lowest total path weight (i. [Read More]
kodeknight 

Hashing, Hash Data Structure and Hash Table

 Posted on July 30, 2013  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Hashing is the process of mapping large amount of data item to a smaller table with the help of a hashing function. The essence of hashing is to facilitate the next level searching method when compared with the linear or binary search. The advantage of this searching method is its efficiency to hand vast amount of data items in a given collection (i.e. collection size). Due to this hashing process, the result is a Hash data structure that can store or retrieve data items in an average time disregard to the collection size. [Read More]
kodeknight 

What is a Complete Binary Tree?

 Posted on July 30, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

A strictly binary tree of depth ’d’ in which all the leaves are at level ’d’ i.e. there is non empty left or right subtrees and leaves are populated at the same level. In a complete binary tree all the internal nodes have equal degree, which means that one node at the root level, two nodes at level 2, four nodes at level 3, eight nodes at level 4, etc, which the below figure represents: [Read More]
Binary Tree  BT  kodeknight  binary-search-tree  BST  Data Structure  Complete Binary tree 

Binary tree traversal: Preorder, Inorder, Post-order, BFS, DFS, Level Order, zig zag order

 Posted on July 30, 2013  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

In order to illustrate the 3 traversals - pre order, in-order and post-order lets take following tree: Preorder traversal: To traverse a binary tree in Preorder, following operations are carried-out (i) Visit the root, (ii) Traverse the left subtree, and (iii) Traverse the right subtree. Therefore, the Preorder traversal of the above tree will outputs: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10 Implementing pre-order traversal [Read More]
inorder  Preorder traversal  Binary Tree  BT  kodeknight  postorder  preorder  incomplete  Inorder traversal  traversal  binary-search-tree  BST  Postorder traversal 

Data Structure Introduction

 Posted on July 29, 2013  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

The basic building block of DATA STRUCTURE are “data” and “information”. So, before discussing data structure, we need to understand what is data and some ground facts about data structure. many people use the terms “data” and “information” as synonyms but these two terms actually convey very distinct concepts.  “data” is defined as a body of facts or figures, which have been gathered systematically for one or more specific purposes [Read More]
kodeknight  Data Structure 

About

 Posted on July 29, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

This is my tech blog related to datastructures and algorithms. I write on this blog to save my searching stuff on google. It acts as my log of all the stuff I went through and saves my time, because I don’t have to search again and again. So all my code logs lies here.

kodeknight 

Legal

 Posted on July 29, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

KodeKnight is for learning and training only. Its not guaranteed that content published is correct. The risk from using it lies entirely with the user. Also the opinions expressed herein are my own personal opinions and do not represent my employer’s view in any way.

kodeknight 

Circular Stack

 Posted on July 29, 2013  (Last modified on August 12, 2020)  |  1 minutes  |  Kinshuk Chandra

There is no diffeence in circular list stack and non circular list stack. The insertion, deletion operation takes place in the same place. So it won’t create any modification in the circular list. Here is the implementation of circular stack in CPP Program in cpp #include <iostream.h> #include <stdlib.h> using namespace std; struct node { int info; struct node \*next; }; int c=0; struct node \*top;int empty() { return((top == NULL)? [Read More]
kodeknight  incomplete  circular stack  stack 

Red Black Tree – Insertion

 Posted on January 7, 2012  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Introduction: Please refer the introduction of RBT here. So, we now know the invariants or properties of RBT which make it rbt :) Insertion of element in RBT or red black tree breaks one of the 4 invariants or properties. So we have to fix it in minimal possible way. To assist us with we have 2 solutions : Flipping the color Right and left rotation Insertion: Insertion begins by adding the node much as binary search tree insertion does and by coloring it red. [Read More]
tree  kodeknight  red-black-tree  RBT  balanced trees  incomplete 

Red Black Tree – Deletion

 Posted on January 7, 2012  (Last modified on August 7, 2020)  |  8 minutes  |  Kinshuk Chandra

Deletion of a node from a red black tree is very difficult. During insertion we selected the color of a new node as red to make it easier. We forced a red violation and fixed it. Red violations are easy to fix, and we took full advantage of that to produce a truly elegant recursive algorithm. When you want to delete a node, you don’t have the option of choosing its color. [Read More]
tree  kodeknight  red-black-tree  RBT  balanced trees