Consider x = 10 and y = 25

CASE1:

If (y <= 0) return x;                           // 25<=0 (false)

                return function (y, x%y);            return function(25, 10)

CASE 2:

x = 25, y= 10

If (y <= 0) return x;                          // 10<=0 (False)

                return function (y, x%y);        // return function (10, 5)

CASE 3:

x =10, y =5

If (y <= 0) return x;                         // 5<=0 (false)

                return function (y, x%y);             //return function(5, 0)

CASE 4:

x = 5, y =0

If (y <= 0) return x;                         // condition true, return 5

                return function (y, x%y);

Output = 5

Which is greatest common divisor of 10 and 25.

So, given program computes GCD of x and y

The correct solution is 'option 1'.

Key Points

  Algo Preorder(tree root)

  {

1. Visit the root node.
2. Traverse the left subtree ( call Algo Preorder(left-subtree) ).
3. Traverse the right subtree ( call Algo Preorder(right-subtree) ).

  }

• Start with a root node 'A' move towards it's left subtree i.e 'B'. And again the node 'B' becomes the root node. Recursively calling by the above function prints the pre-order of the above Tree. 

Thus, the correct answer is: A B D F E C G I H J K L

Additional Information

• To build a copy of the tree, a preorder traverse is used. Preorder traversal is often used to get the prefix on an expression tree.
•  Here, some tree traversal techniques and flow.
• In-order     -  F D B E A I G C J H L K
• Pre-order  -  A B D F E C G I H J K L
• Post-order - F D E B I G J L K H C A
• Converse Inorder - K L H J C G I A E B D F
• Converse Preorder- A C H K L J G I B E D F
• Converse  Postorder- L K J H I G C E F D B A

The stack is an abstract data type that follows an order LIFO (last in first out) to evaluate any expression.

The element that is inserted at the last into the stack will be the first to get out of the stack.

Application of the stack:

1) Converting infix to postfix/prefix expression

2) parenthesis matching

3) Expression evaluation etc.

Explanation:

Only one stack is enough to evaluate any expression or to convert one form to another form of expression.

Suppose we have a postfix expression: 15 3 * 10 – 5 /

For evaluating this:

1) Push 15 in the stack, push 3 in the stack

2) when * operator comes, pop 15 and 3 from the stack

3) Push 15 * 3 = 45 in the stack

4) push 10 in the stack

5) when – operator occurs, pop 45 and 10 from the stack

6) push 45 – 10 = 35 in the stack

7) push 5 in the stack

8) when / operator comes, pop 35 and 5 from the stack

9) Push 35 / 5 = 7 in the stack

• Breadth-first search (BFS) and Depth First Search (DFS) is an algorithm for traversing or searching tree or graph data structures.
• Breadth First Search (BFS) algorithm traverses a graph in a breadthwise manner and uses a queue to remember to get the next vertex to start a search, when a dead end occurs in any iteration.
• Depth First Search (DFS) uses Stack data structure. DFS uses backtracking technique. Remember backtracking can proceed by Stack.

Consider x = 10 and y = 25

CASE1:

If (y <= 0) return x;                           // 25<=0 (false)

                return function (y, x%y);            return function(25, 10)

CASE 2:

x = 25, y= 10

If (y <= 0) return x;                          // 10<=0 (False)

                return function (y, x%y);        // return function (10, 5)

CASE 3:

x =10, y =5

If (y <= 0) return x;                         // 5<=0 (false)

                return function (y, x%y);             //return function(5, 0)

CASE 4:

x = 5, y =0

If (y <= 0) return x;                         // condition true, return 5

                return function (y, x%y);

Output = 5

Which is greatest common divisor of 10 and 25.

So, given program computes GCD of x and y

Concept:

• A stack is an ordered list in which insertion and deletion are done at one end, called a top.
• The last element inserted is the first one to be deleted. Hence, it is called the Last in First out (LIFO) or First in Last out (FILO) list.

Explanation:

A recursive problem like the Tower of Hanoi can be rewritten using system stack or user-defined stack

Recurrence relation of tower of Hanoi:  T(n) = 2T(n - 1) + 1 

Additional Information

Number of moves required for n disc in a Tower of Hanoi is 2n – 1 = 27 – 1 = 127. 

Stack underflow happens when one tries to pop (remove) an item from the stack when nothing is actually there to remove.