Faculty of Computer Science and Engineering
Department of Computer Science

1/4
DATA STRUCTURES & ALGORITHMS
Tutorial 3 Questions
Recursion and Binary Tree

Part 1. Recursion
Required Questions

Question 1.
What would be the contents of queue Q1 after the following code is executed and the
following data are entered?
1 Q1 = createQueue
2 S1 = createStack
3 loop (not end of file)
1 read number
2 if (number not 0)
1 pushStack (S1, number)
3 else
1 popStack (S1, x)
2 popStack (S1, x)
3 loop (not empty S1)
1 popStack (S1, x)
2 enqueue (Q1, x)
4 end loop
4 end if
4 end loop
The data are: 9, 5, 10, 4, 0, 5, 4, 6, 8, 67, 32, 25, 51, 0, 54, 23, 20, 6, 10

2 Q = creatQueue
3 while(not empty(S))
1 popStack(S,temp)
2 enqueue(q,temp)
4
while(not empty(q))
1
reverse(Q)
5
dequeue(q,temp)
2
enqueue(Q,temp)
6
return Q
End append

Faculty of Computer Science and Engineering
Department of Computer Science

2/4
Return element of s is appended into q with the same order. For
example if q = {1,2,3}, s = {4,5,6} then q = {1,2,3,4,5,6} after
append.
Queue {front rear}
Stack {bottom top}

Question 3.
Consider the following algorithm:

Algorithm fun1 (x <integer>)

Develop recursive algorithm for the following problems.

a. Find and return an element in an array, where the array and its size are given as
parameters. This element should be in middle position when the array is re-
ordered increasingly.
8
17
47
(2*(2*2
Algorithm compute (x <integer>)
1 if (x =0)
1 return (0)
2 else
1 return (n+compute(n-1))
3 end if
aánh
Algorithm compute (val a <array>, val n <integer> )
1. if (n=0)
1 return a[0]
2.else
return (compute(a,n)>compute(a,n-1))?compute(a,n):compute(a,n-1)
3233
6,5,4
4,5,6

Faculty of Computer Science and Engineering
Department of Computer Science

3/4


c.
Algorithm pow (val a <float>, int b <integer>)
Pre a,b >=0
Return the power a
b
. The only two arithmetic operations that
you are allowed to use in this problem are multiple * and
subtraction -Question 7.
Develop fully recursive algorithms for the functions reverse and append in Question 2 return (start<=end)?end:listnumber(start-1,end)
if(b=1) return a;
else
return a+mul(a,b-1)
return (b==1)?a:a+mul(a,b-1)
return (b==1)?a:a*pow(a,b-1)
append (Queue*Q,Stack *S)
Pre true
Return a reversed queue of q
S=new Stack();
Q = new Queue();
while(S->top!=NULL)
popStack(S,temp)


algorithm generateBSTfromList (val list <List>)
This algorithm generate a BST from the input list
Pre
Post the BST is built by inserting elements in the list into an initial empty tree
one-by-one from the beginning of the list.
Return the BST
end generateBSTfromList Advanced Questions

Question 11.
Devise an algorithm that takes two values, a and b such that a < b, and which visits all
the keys x in a binary search tree such that a  x  b.

1
2
3
4
5
6
7
1
2
3
4
5
6
7

1. return recursive_Insert(subroot->left, DataIn)
3. else if (DataIn.key > subroot->data.key)
1. return recursive_Insert(subroot->right, DataIn)
4. else
1. return duplicate_error
5. End recursive_Insert