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 Program C++ Program Java program Python Program C Program C++

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

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 queue Dequeue 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 th

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++ Program Java program Python 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 List Method to add element at the end of the List Method to display the Linked List.

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. In this tree, the lowest common ancestor of the nodes  x  and  y is marked in dark green.  Other common ancestors are shown in light green. 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++ Program Python 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

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++ Program Python 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++ Program Python 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 field left link  right link For 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

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 field left 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 searc

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 field left link  right link Each node in the binary tree has the following properties Data of the left node is less than the parent node Data 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 no

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 number Step 3: Replace the bigger number by the remainder.  Step 4: Repeat above steps until the smaller number becomes 0 C++ Program Java program Python Program C++ Program Java Program Python Program Sample input and output to check

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 List Method to add an element at the end of the List Meth

Home Page

List of All Programs The Following is the List of all the programs on my Blog Math Programs Square Root of a number using Babylonian Method Finding The Next Smallest Palindrome Finding the Armstrong Numbers Factorial of a number GCD using Euclid's Algorithm Check if a number is Fibonacci Number or not LCM of 2 numbers Trailing Zeros in factorial of a number Sorting Algorithms Bubble Sort Algorithm Selection Sort Algorithm Insertion Sort Algorithm Shell Sort Algorithm Counting Sort Algorithm Linked List Programs Simple Singly Linked List Linked List in C++ Linked List in Python Linked List in Java Doubly Linked List Finding Kth element from the end of Linked List Delete a node from Linked List Delete Kth element from the end of Linked List Rotate Linked List in an Anti-clockwise direction Reversing first K nodes of a Linked List Binary Search Tree Left View of Binary Tree Righ

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 Recursion Backtracking  Memory management  Activation records etc To know more about Stacks click here  The following program is to implement a stack using an array with maximum size of 20. C Program C++ Program Java program Python 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 Gr