Sunday, that wasn't like a SUNDAY..

It was 10:00 am in the morning of sunday; 16th september 2007 but that was not like other sundays! We (the 2007 batch NCSTians) were watching each other's faces while sitting in the lecture hall for the extra session of DS which was going to be start in a while by our Raman Sir..The irony of the title is also true for him, as he too was sacrificing his sunday!

But the lecture was really a GOLDEN GLIMPSE towards what we learnt so far in that subject including some extra applications as well as important do's and don'ts.. And this time my blog is dedicated to that lecture, I mean I m trying to cover a little part of it (little because what I got was while several iterative rounds of sleeping-awakening)! Oh wait, dont estimate that I am trying to say that lecture was boring, THAT WAS AWESOME but the SUNDAY WAS ON ITS FULL and we generally used to spend our time in some other manner on sundays, if that session hadn't there!

So, Raman Sir is requested to forgive me if I go wrong at some point in it and to rectify those mistakes so that people; like me can take benefits of this blog. Sorry to non-NCSTian friends this time for being specific about NCST!

Let me pray to God and allow me to start:-

Variable selection in recursion:

Actually Recursion refers to a function calling itself. Whenever we need to check the status of a variable after each and every pass, we declare it as GLOBAL variable. If the need of the variable is just satisfied after each pass then we declare it LOCAL.

DFS & BFS:

It refers to Depth First Search and Breadth First Search. In DFS (if we talk about in terms of DS like TREE), as the name suggests, we first go to the deep of that node explore its children and then we explore it and its siblings. We implement it through STACKS..

While in BFS, we first explore the siblings of a node and after that we do the saem to its children. We can implement it by the help of QUEUE.

Application of Stack in Postfix notation:

Suppose we have an expression in postfix notation: "(2 3 + 5 6 * -)" then to solve such kind of expression we take the help of stacks. First the operands(2,3 etc.) will be pushed into stack. We popped two operands( or one operand) as soon as a binary operator(+, - etc.) (or unary operator like ++,-- etc)comes!Then push the result into the stack.

For example::-

Push 2,3 first. As + comes, both pop up and added which results into 5 into stack. then push 5,6. As * comes pop 5,6 and push the result 30 into the stack, as - appears pop those remained values 5,30 and perform the -.Which results into Final value of (-25).

Queue and Circular Queue:

As we know, queue can be implemented only with the help of two varibles front and rear while for the implementation of Circular queue we need to have these variables with some other like size, count, apart from it we also perform modulus operation for overcoming the limitation of normal queue which comes into picture when front becomes equal to rear and it shows the queuefull exception while it is totally empty.

We can also implement it without those extra variable but tehn code becomes little complex. In that case we have to check whether front crosses the rear(for queueEmpty exception) or the rear crosses the front(for queueFull exception).

Deletion in tree:

The hardest operation in tree, I suppose is deletion. While doing it, we should chech the following steps first:

• Determine Node to be deleted is the leftnode or the rightnode of its parent.(say LCorRC)

• When leaf is to be deleted-First findnode. then findparent, check LCorRC. Then delete it.

• When Node to be deleted has only one child-First findnode. then findparent, check LCorRC. Finally delete it by attaching LC (or RC which is not nul) to its parent!

• When Node to deleted has two children- Well after performing above operations I think its not very difficult to do this operation, actaully I ve to cover up all other stuffs so IM LEAVING THIS TO YOU PEOPLE to consult from any good book.(This is the best way to GET RID OF IT...hahahahahaha)

Let me provide a scratch of code to elaborate the following:-

Tree to array conversion:

It's supposed that you already have the class Node and int arr[].
public void t2a(node n,int p)
{
if(n!=null)
{
arr[p]=n.data;
t2a(n.left,2p);
t2a(n.right,2p+1);
}
}

Find the node in Binary search tree & in Binary tree:
//IN BINRAY SEARCH TREE..
public Node find( Node n, int i)
{
if(n!=null)
{
if(n.data==i)
return n;
else if(n.data>i)
return find(n.left,i);
else
return find(n.right,i);
}
return null;
}
//IN BINARY TREE..
public Node find(Node n, int i)
{
if(n!=null)
{
if(n.data==i)
return n;
Node temp=find(n.left,i);
if(temp!=null)
return temp;
return find(n.right,i);

}
}

for further queries click onto:::--http://gnyan.ncb.ernet.in/~dsalfac/