Run Graphics programs in Dev C++

Many people uses Turbo c++ to run c and c++ programs. More people want to do graphics programs.If they use windows 7 64 bit they may not be able to run Turbo c++. Dev C++ is more user friendly .Here you can see how to run graphics programs in Dev C++.

Steps

1: Download graphics.h
2:Download libbgia
Download this from here .
3:Copy the graphics.h file and go to the directory C\ Dev-Cpp\include
4:paste it

Read more

Heaps : Algorithms

Heaps

Heap is a kind of data structures based on complete tree principle. By definition, a complete binary search tree of N levels has at least 2^N-1 nodes in it. Heap is nearly complete tree. Heap maintains a property called as heap property which holds across all nodes of the heap. 
There are two kinds of heaps we frequently deal with :

Max Heap : It maintains the property that every parent node is greater than its children. Root of the max heap is greatest element.

Min Heap : It maintains the property that every parent node is less than its children. Root of the min heap is least element.

Read more

Binary Search Tree : Bottom up approach to problems

Introduction

In Binary Search Tree, there is a class of problems which have solutions with similar structure.

These problems involve deletion of complete BST, mirroring a BST, replacing parent node with sum of children etc. In this post we would discuss the structure of the solution and their execution in run time in detail. Once this strategy is mastered, most of the BST problems can be solved easily.

Problem statement

1. Delete a given Binary Search Tree

2. Mirror a give Binary Search Tree i.e. Left child should become right and right should become left.

3. Replace the value of a node with sum of its children nodes.

Analysis

Problem 1 :Delete a BST

To delete a binary search tree, we start with leaf nodes. Once all leaf nodes are deleted, we move to upper layer which in turn would have become leaf nodes now. We continue to do so till the time we reach root node and then delete root node.

Algorithm

1. Start with root node.
2. If root is null, return.
3. Check if there is left child, delete the sub tree with root as left child.
4. Check if there is right child, delete the sub tree with root as right child.
5. Delete the root node.

Complete code

void delete_BST(Node *root){

Read more

Find Closest Element in Binary Search Tree

Find Closest Element in Binary Search Tree

The problem of finding a closest element in a tree to a given value is another case where we can use the property of binary search tree.

Problem statement 

Given a Binary Search Tree and a value, find the closest element to the given value in BST.

Analysis

Simple approach is to go to all elements of BST and find out the difference between the given value and value of the element. Get the minimum value and add or subtract that minimum value from the given value, we would get the closest element in the BST.

Do we really need to scan all the nodes? No we don't need to.
Let's consider it case by case.
Case 1 : If the value of the node under consideration is equal to value, then our minimum difference would be zero and closest value would the value itself.

Case 2 : If the value of the node under consideration is greater than given value.
By virtue of BST, we know that nodes on the right side of the given node would be greater than this. Hence the difference between the given value and all nodes on the right side would only increase. Hence there is no element on the right side, which is closer than the node itself. Hence the right sub tree is discarded.

Case 3 : If the value of the node under consideration is less than the given value.
Again same logic applies as in case 2. Since all elements in left sub tree are less than the node, difference between given value and the nodes on left side would only increase. Hence we can safely discard the left sub tree.

Algorithm

1. Start from the root, initialize min to MAX_INT 

Read more

Deleting a Node in Binary Search Tree

Introduction

This post elaborates how we can delete any node in a binary search tree and maintain its binary search tree property.

Problem statement 

Given a number K and a binary search tree, delete the node with value K and also maintain the binary search tree property.

Analysis

First problem is to locate the the node. Once the node is located, there are three cases to be considered before we delete the node.

Case 1 :

If the given node is leaf node. Straight forward, delete the node. 

For example, tree is like given below and we need to delete 4.

It would be deletion of node 4 and setting the left child of 6 as NULL.

Case 2 :

If the node is not leaf node and there is right sub tree to it. In this we would replace the deleted node by the in-order successor of the node in BST. Free the in-order successor node.

Read more

Check if a given tree is Binary Search Tree or not

Introduction

How do we know that a given binary tree is a binary search tree?

Definition of BST:

All the nodes on the left side of a given node are smaller and all nodes on the right side are greater than the given node.

So, essentially, any tree is a binary search tree if both its left sub tree and right sub tree are binary search tree and root satisfy the binary search tree condition.

So, tree is binary search tree if

1. Left sub tree is binary search tree

2. Right sub tree is binary search tree

3. Value of root is greater than max in left sub tree and less than minimum in right sub tree

No further analysis is required for this problem.

Read more

Binary Search Tree : Level order printing

Print nodes of a tree in level order

Problem statement 

Print nodes of a tree level wise i.e. nodes at same level should be printed together.

For example, in following tree output should be 

10,6,15,4,7,13,17

Read more