Expression Trees

Step 1 : Convert the given expression to postfix form
Step 2 : Read one symbol at a time from the postfix expression
Step 3 : Check whether the symbol is an operator or operand.
(i)If it is an operand,create a one node tree and push a pointer on the stack.
(ii)If it is an operator,pop two pointers from the stack namely T1 and T2 and form a new tree with Root as operator and T2 as left child and T1 as right child.Push the pointer to this new tree on to the stack.
Step 4 : Repeat the Steps till the end of the expression.

Depth First Search

Step1 : Choose any node in the graph,designate it as search node and mark it as visited.
Step2 : Using Adjacency matrix of the graph,find a node adjacent nodes to the search node that has been not yet visited and designate that node as the search node and mark it as visited.
Step3 : Repeat Step2 using the new search node.If no nodes satisfying Step2 is found,return to the previous search node and continue from there.
Step4 : When a return to the previous search node in Step3 is impossible,the search from the originally chosen node is complete.
Step5 : If the graph still contains unvisited nodes,choose any node that has not yet been visited and repeat Step 1 to 4.

Breadth First Search

Step1 : Choose any node in the graph,designate it as search node and mark it as visited.
Step2 : Using Adjacency matrix of the graph,find all unvisited adjacent nodes to the search node and enqueue them on to a Queue
Step3 : Then the node is dequeued from the queue.Mark the node as visited and designate it as the source node.
Step4 : Repeat step2 and step3 using the new search node.
Step5 : Repeat these process until the queue which keeps track of the adjacent nodes is empty.

Infix to Postfix using Stack

Step1 : Push the delimiter “#” onto the stack.
Step2 : Read the characters one by one from the given infix expression

1. If the character is an operand ,place it on to the output.
2. If the character(ch) is equal to an operator or any opening symbol,then pop a character (pch)from the stack.If the stack priority of pch >= infix priority of ch ,then put pch in the output and push th ch into stack,if the condition didn‟t get satisfied then push pch and c into the stack.
3. If the character is a closing symbol,pop all the operators from the stack till it encounters its corresponding opening symbol and place it on the output and discard both the opening and closing symbols.

Step3 : Repeat all the steps till # is encountered

Topological Sort (only for directed Acyclic Graph)

Step1 : Find the indegree of all the vertices of the graph.
Step2 : Place the vertices whose indegree is „0‟ on an empty queue.
Step3 : Dequeue the vertex V and decrement the indegrees of all its adjacent vertices.
Step4 : Enqueue the vertex whose indegree has fallen to „0‟.
Step5 : Repeat from step3 untill the queue becomes empty.
Step6 : The topological sorting order is the order in which the vertices are dequeued.

Towers of Hanoi Using Stack (Recursive Solution)

(The problem is moving a collection of N disks of decreasing size from one pillar to another.The movement of the disks is restricted by the following rules:
Rule1: Only 1 disk could be moved at a time.
Rule2: No larger disk could ever reside on a pillar on top of a smaller disk.
Rule3: A 3rd pillar can be used as an intermediate to store one or more disks,while the disks are moved from source to destination )

Let N represent the number of disks
Step1: If N=1,move the disk from A to C.
Step2:

1. If N=2,move the 1st disk from A to B,
2. Then move the 2nd disk from A to C,
3. Then move the 1st disk in B to C.

Step3: If N=3,repeat step2,to move the first two disks from A to B using C as intermediate.
Then move 3rd disk from A to C.Then repeat the step2 to move 2disks from B to C using A as intermediate

In general,to move N disks,apply recursive technique to move (N-1) disks from A to B with C as an intermediate.Then move the Nth disk from A to C.Then again apply the recursive technique to move (N-1) from B to C using A as intermediate.