# Archive for category Programming

### How to get Mirror Image of a Binary Search Tree?

Posted by encrypt3d in Data Structures, Programming on September 21, 2010

What do you mean by Mirror image of a Binary tree? It means, another binary search tree that is a mirror image of the given one.

This is a recursive solution for this problem, just swap the left and right subtrees for each node recursively. Let me know if you have problem understanding it.

`struct tnode *mirror(struct tnode *p){`

if(p == NULL)

return p ;

else{

mirror(p->left);

mirror(p->right);

struct tnode *temp;

temp=p->left;

p->left=p->right;

p->right=temp;

}

return p;

}

### How to delete minimum node from a Binary Search Tree?

Posted by encrypt3d in Binary Tree, Data Structures, Programming, Simple Ones!! on September 21, 2010

This is going to be simple. As you already know that the data in Binary Search Tree is already organized, you know exactly where to find the node with minimum value. If you start from the root and keep going to left till you can traverse the tree, the last node is going to be the minimum one. Here is the C++ code for that. I am trying to put the codes in proper indentation, but its not working for me with the blog.

`struct tnode *delmin(struct tnode *p){`

struct tnode *temp=p;

while( temp->left->left != NULL){

temp = temp->left;

}

temp->left=NULL;

delete(temp->left);

return p;

}

Now try to write the code for deleting the maximum one. Isn’t it quite simple and obvious?

### How to insert a node in Binary Search Tree?

Posted by encrypt3d in Binary Tree, Data Structures, Programming on September 21, 2010

Binary Search Tree is very important data structure in computer science. I am trying to cover most of it in the article. You should be able to answer following questions after reading (and understanding) the article.

- What is Binary Search Tree?
- Why Binary Search Tree is used for?
- How to insert a node in a Binary Search Tree?

- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.

**Structure of Binary Search Tree Node:**

** **

`struct tnode {`

int data;

struct tnode *left;

struct tnode *right;

};

Data is an integer, which will contain the actual data and left and right are again the Binary Search Tree nodes containing left and right subtrees.

**How to insert a Node in Binary Search Tree:**

While inserting a new node to binary search tree, we need to maintain the basic property of Binary Search Tree . Traverse through the tree and find out the correct position for the given node.

struct tnode *insert(struct tnode *p , int val){ if(p==NULL){ p = (struct tnode *)malloc(sizeof(struct tnode)); p->data = val; p->left = NULL; p->right = NULL; }else{ struct tnode *q,*temp; q=p; temp=p; while(q != NULL ){ temp= q; if( val >= temp->data) q=temp->right; else q=temp->left; } struct tnode *n; n= (struct tnode *)malloc (sizeof(struct tnode)); n->data =val; if( val >=temp->data ) temp->right =n; else temp->left = n; } return p; }

### Floyd Warshall Algorithm!

Posted by encrypt3d in Programming on August 6, 2007

The **Floyd-Warshall Algorithm** is an efficient algorithm to find all-pairs shortest paths on a graph. That is, it is guaranteed to find the shortest path between every pair of vertices in a graph. The graph may have negative weight edges, but no negative weight cycles (for then the shortest path is undefined).

This algorithm can also be used to detect the presence of negative cycles—the graph has one if at the end of the algorithm, the distance from a vertex *v* to itself is negative.

The problems form ACM UVA , 523 and 627

Assuming that a[i][j]=-1 where there is no path. p[i][j] is used for tracing the shortest path. The Algorithm is just an application of Dynamic Programming. INF is considered to be a very big integer.

`for(int i=0;i<n;++i)`

for(int j=0;j<n;j++)

if (a[i][j]==-1)

{

a[i][j]=INF;

}

for(int i=0;i<n;i++)

for(int j=0;j<n;j++)

p[i][j]=i;

for(int k=0;k<n;k++)

{

for(int i=0;i<n;i++)

{

for(int j=0;j<n;j++)

{

if(a[i][j] > a[i][k]+a[k][j])

{ a[i][j]=a[i][k]+a[k][j];

p[i][j]=p[k][j];

}

}

}

}

### Longest path!

Posted by encrypt3d in Acm, Programming on August 5, 2007

The problem taken form acm uva site , Longest Path

Since we need to know the longest path for a source node given, the graph of cities to be traversed in DFS. The Depth First Traversal visits all nodes reachable from the source node. Here is the function needed for DFS in this problem.

`void dfs(long snode)`

{

long i;

if(sum>max)

{

max=sum;

p=snode;

}

for(i=0;i<num;i++)

{

if(n[snode][i]==1&&visited[snode][i]==0&&i!=start)

{

visited[snode][i]=1;

sum++;

dfs(i);

sum--;

visited[snode][i]=0;

}

}

}