Skip to main content

Posts

Showing posts from 2016

Bubble sort Algorithm

Bubble sort is the most simple sorting technique used to sort arrays , linked list etc. It is an algorithm that keeps traversing the list until the list is completly sorted. Bubble sort has been occasionally referred to as a "sinking sort". The idea being that the larger elements are heavier hence they sink to the bottom of the list and smaller elements being light bubble to the top of the list.

Algorithm

In bubble we keep comparing 2 adjacent elements and swap their places is they are not in correct order.

Performance

Bubble sort being a simple algorithm works fine when the size of the data is small but its performance decreases as the size of the data increases, hence Bubble is used only when number of elements is small or only some elements are out of order.

To know more about bubble sort, its performance, complexity and comparisons to other sorting methods click Here.





C ProgramC++ ProgramJava programPython Program C Program C++ Program Java Program Python Program Sample input …

Stack implementation using Linked List

Stack is a data structure it serves as a collection of elements. It has 2 principle operation push and pop.Stack works on the principle of  Last In First Out or LIFO i.e the element that is entered last is removed first. To do this is has 2 methods  push() :  push operation pushes the element on the top.pop() :  pop operation removes the element on the top. This can be seen in  the below image.



Linked list is a simple linear data structure formed by collection of data elements called nodes. Each node consists of a data element and link field.The data field consists of element and link field consists of address of next element.

To know more about Stack Data Structure click here
To know more about Linked List click here
To view Simple Linked List implementation click here 
Now inorder to implement Stack using linked list we need to implement push and pop operation in Linked List. Push and pop can be implemented by using other already implemented functions of Linked List like addToStart, …

Queue implementation using Linked List

Queue is a data structure that serves as a collection of elements. It follows the policy of FIFO i.e first in first out. To follow this it has 2 principle functions

Enqueue  function is used to add an element to the rear of the queueDequeue function is used to remove an element from the queue


Linked list is a simple linear data structure formed by collection of data elements called nodes. Each node consists of a data element and link field.The data field consists of element and link field consists of address of next element.

To know more about Queue Data Structure click here
To know more about Linked List click here
To view Simple Linked List implementation click here 
Now inorder to implement Queue using linked list we need to implement enqueue and dequeue operation in Linked List. Enqueue and dequeue can be implemented by using other already implemented functions of Linked List like addToEnd and remove functions.

Here is the Complete code for the implementation
C++ ProgramPython Progr…

Check if a number is Fibonacci number

Fibonacci numbers are numbers such that each number is the result of adding two preceding numbers. A sequence of such numbers is called as fibonacci numbers.
Fibonacci sequence start with 1, 1 as the first 2 terms. Fibonacci sequence is 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , ....
If we want to check if a number is a fibonacci number or not we only need to check if  5*number*number - 4  or 5*number*number + 4 is a perfect square or not.
To see the derivation of the above formula click here.
C++ ProgramJava programPython Program C++ Program Java Program Python Program Sample input and output to check the program
You might also be interested in

Finding Factorial of a number
Finding the next smallest Palindrome
Implement Binary Search Tree
Implement Linked List
Implement Doubly Linked List

Simple Doubly Linked List

Doubly Linked list is a simple linear data structure formed by collection of data elements called nodes. Each node consists of a data element and 2 link fields. The Left Link gives the address of the previous node and right link gives the address of next node.


Each Linked List starts with a head node that points the first node of the List. Unlike arrays Doubly linked lists are not stored in contagious memory locations rather the are stored at any empty place in memory and the address of the next node is stored in the link field. Also you don't need to declare the size of the linked list at the time of initialization you can dynamically keep adding elements to the linked list.




Click for complete information on Doubly Linked List 
The following implementation of the linked list has the following methods implemented :
Method to add element at the start of the ListMethod to add element at the end of the ListMethod to display the Linked List.

Python Program Python Program

This is a Simp…

Lowest Common Ancestor of nodes in BST

This post is about finding the lowest common ancestor of 2 nodes in a binary search tree.

Lowest Common Ancestor of 2 nodes x and y is the node that has both x and y as its desendents. The below image is might help you to understand the above statement.


If you want to know more about Lowest Common Ancestor click here.
To see more programs about BST and other Data Structures click here

C++ ProgramPython Program C++ Program Python Program Sample input and output to check the program


You might also be interested in

Binary Search Tree in Python
Binary Search Tree in C++
Height of Binary Search Tree
Insert ,Search and Display Binary Search Tree
Leaf Nodes of Binary Search Tree
Minimum and Maximum Elements in BST

Minimum and Maximum element in Binary Search Tree

Minimum and Maximum elements of a Binary Search Tree can be found very easily.
If we see the insertion method of a Binary Search Tree we see that if the new element is greater than the current node data then we move to its right subtree ,Similarly if the new Element is less than the current node data we move to its left subtree.

Hence we can easily infer that the smallest element of the Binary Search Tree must be the leftmost node of the tree.
Similarly we can say also infer that largest element should be the rightmost node of the tree.

The following image makes the above statement more clear.




In the above figure we see that 1 is the smallest element of the tree which is also the leftmost node of the tree and 14 is the largest element of the tree is rightmost node of the binary tree.

To know more about binary search tree click here.

To see more operations of binary search tree Visit the following Links

Binary Search tree in C++
Binary Search tree in Python


C++ ProgramPython Program C++ …

print leaf nodes of binary search tree

Leaf nodes of binary tree are the nodes with no children or no subtrees.
They have both left and right links as null.


In the above image nodes 1,4 ,7 ,13 have no sub-trees hence they are the leaf nodes.

Leaf nodes can be found easily by traversing the tree in inorder way and the printing the nodes that have no left or right subtrees.


C++ ProgramPython Program C++ Program Python Program


You might also be interested in

Minimum & Maximum Element in BST
Binary Search Tree in Python
Binary Search Tree in C++
Insert ,Search and Display Binary Search Tree
Height of Binary Search Tree
Linked list in Python

height of binary search tree

Height of the binary search tree is defined as the number of nodes in the longest path from the root node to leaf node.



In the above image one of the longest paths is 8 --> 10 --> 14 --> 13, containing 4 nodes hence the height of the binary search tree is 4. One thing that should be noted is that a tree with only root node has height 1 and not 0.
In the following the height of the left and right subtree is compared and the larger value is returned.

C++ ProgramPython Program C++ Program Python Program


You might also be interested in

Singly Linked List
Binary Search Tree in Python
Binary Search Tree in C++
Insert ,Search and Display Binary Search Tree
Print Leaf nodes of Binary Search Tree
Linked list in Python

Binary search tree in cpp

Binary Search Tree is a rooted binary tree. Its subtrees have certain properties. Each element of the binary tree is a node that has mainly 3 fields,

data or element fieldleft link right linkFor each node in a binary search tree, the data of the left node is less than the parent node and data of the right node is greater than the parent node.



It can be seen in the image above that the data in the left child node is less than the data of the parent node and data of the right child node is greater than the parent node.
There are a lot of advantages of using the binary search tree data structure, they are related to searching, sorting, using them as priority queues, etc.
To know more about binary search tree click here.
The following program has the following operations implemented isEmpty() : method that checks if the tree is empty.getRoot() :  method that returns the root element of the binary search tree.insert() : Insertion in Binary search tree.search() : Method for Searching a element in…

binary search tree in python

Binary Search Tree is a rooted binary tree. Its subtrees have certain properties. Each element of the binary tree is a node that has mainly 3 fields,

data or element fieldleft link right link For each node in binary search tree , the data of the left node is less than the parent node and data of the right node is greater than the parent node.



It can be seen in the image above that the data in the left child node is less than the data of the parent node and data of the right child node is greater than the parent node.
There are a lot of advantages of using the binary search tree data structure, they are related to searching , sorting , using them as priority queues , etc.
To know more about binary search tree click here.
The following program has the following operations implemented isEmpty() : method that checks if the tree is empty.getRoot() :  method that retuens the root element of the binary search tree.insert() : Insertion in Binary search tree.search() : Method for Searching a el…

binary search tree insert search and display

Binary Search Tree is a simple data structure which is very often used to solve a lot of different problems based on searching and sorting, and also it is a very popular topic for programming coding challenges and interview questions.
Binary Search Tree is a rooted binary tree. It is basically a collection of nodes which are linked to each other. now, you may ask what is a node? Each element of the binary tree is a node that has mainly 3 fields,


data or element fieldleft link right link
Each node in the binary tree has the following properties
Data of the left node is less than the parent nodeData of the right node is greater than the parent node.
Below is an example image for a binary search tree




It can be seen in the image above that the data in the left child node is less than the data of the parent node and data of the right child node is greater than the parent node. For example, let us consider 8 as the parent node, then we can see that all the nodes that are to the left of it have a …

gcd using euclids algorithm

GCD stands for greatest common divisor. GCD of two numbers is the greatest number that divides both numbers without leaving a remainder. Euclidean algorithm for finding the gcd is based on the principle that the gcd of two numbers does not change if the larger number is replaced by its difference with the smaller number.
Let us consider the example of 206 and 40, we find that 2 is the gcd of 206 and 40 also according to the above statement the gcd of 166 (206 - 40) and 40 is also 2.

To know more about GCD click here.

In the below program we follow the below steps

Step 1: In each iteration calculate the quotient Step 2: Then subtract the product of quotient and the smaller number from the bigger numberStep 3: Replace the bigger number by the remainder. Step 4: Repeat above steps until the smaller number becomes 0





C++ ProgramJava programPython Program C++ Program Java Program Python Program Sample input and output to check the program


You might also be interested in 

Finding factorial of a num…

Singly Linked List

A linked list is a simple linear data structure formed by a collection of data elements called nodes. Each node consists of a data element and link field.





There is a head node that points to the starting of the linked list.
this diagram shows a simple representation of the linked list.






A linked list can be used to implement stacks, queues, list, associative arrays, etc. 
Unlike arrays linked lists are not stored in contagious memory locations rather they are stored at any empty place in memory and the address of the next node is stored in the link field. Also, you don't need to declare the size of the linked list at the time of initialization you can dynamically keep adding elements to the linked list.
Click for complete information on Linked List 
The following implementation of the linked list has the following methods implemented :
Method to add an element at the start of the ListMethod to add an element at the end of the ListMethod to display the Linked List Method to delete an elemen…

Home Page

Stack implementation using array

A stack is a data structure it serves as a collection of elements. It has 2 principle operation push and pop. The push operation pushes the element on the top and the pop operation removes the element on the top. This can be seen in the below image.


Stack works on the principle of  Last In First Out or LIFO i.e the element that is entered last is removed first. Stacks can be implemented using arrays as well as linked list. There are a lot of applications of Stacks like RecursionBacktracking Memory management Activation records etcTo know more about Stacks click here 

The following program is to implement a stack using an array with maximum size of 20.


C ProgramC++ ProgramJava programPython Program C Program C++ Program Java Program Python Program


You might also be interested in 

Linked List in python
Linked List in C++
Finding the next Smallest Palindrome
Finding factorial of a number
Bar Graph in C using dda Line generation algorithm