## What is the height of the tree?

### computer science

##### Description

Question 1: (15 marks)

Consider the following recursive method:

public static int niceOne(int n){

if(n<10)

return n;

else

return(n%10)+ niceOne(n/10);

}

a-    Trace the above recursive method for n=3524    (10 marks)

You should show all the recursive steps (composition and decomposition)

b-    Write the complete program that includes the above method and the necessary statements to print the returned value n. Include a screenshot that shows the code and the output. (5 marks)

Question 2: (15 marks)

Suppose that we have three stacks s1, s2 and s3 of size 6, where stack s2 and s3 are initially empty and stack s1 having the elements {1, 2, 3}, where 1 is at the bottom.

Draw the three stacks after executing the following piece of code.

while(!s1.isEmpty()){

s2.push(s1.peek());

s3.push(s2.peek());

s2.push(s1.pop());

}

Question 3: (20 marks)

Given the following adjacency list for a graph G:

a)    Draw the graph G.

b)    Draw the adjacency Matrix representation of the graph G.

c)    Name two cycles in the above graph.

Question 4: (20 marks)

Given the following numbers found in an array: 8, 7, 1, 4, 3, 9

a)    Use insertion sort to sort the original list of numbers. (10 marks)

b)    Use bubble sort to sort the original list of numbers.    (10 marks)

Question 5: (30 marks)

Answer the following set of questions using the below binary tree:

a)    What is the height of the tree? (3 marks)

b)    What is the depth of node 12? (3 marks)

c)    Give the pre-order traversal of the tree. (8 marks)

d)    Give the in-order traversal of the tree. (8 marks)

e)    Give the post-order traversal of the tree. (8 marks)