How to get Mirror Image of a Binary Search Tree?

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?

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?

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?

A  Binary search tree (BST) or ordered binary tree is a node-based binary tree data structure which has the following properties:

• 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.

Both the left and right subtrees must also be binary search trees.

Generally, the information represented by each node is a record rather than a single data element. However, for sequencing purposes, nodes are compared according to their keys rather than any part of their associated records.

The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.

Binary search trees are a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays.

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!

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!

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;
}
}
}