Question

The following two algorithms claim to solve the same problem. To do so, the two algorithms receive as in input argument a reference pointing to a root of a tree: a) For the following Binary Tree: What is returned by the function call A2(root)? (5.0 marks) ALGORITHM 1 Function A1(root) ( == ) − 1 = . = () (, ) ℎ (!()) = () (. < ) = . (,. ) (,. ℎ) () ℎ End of function A1 ALGORITHM 2 Function A2(root) ( == ) − 1 = ℎ (. ! = ) = . ℎ . End of function A2 Note: the function ENQUEUE only inserts a new element in the queue if this element is different from NULL.For the Binary Tree in part (a), what is the content of the queue immediately before returning from the execution of function A1(root)? (5.0 marks) c) Re-write the function A2, in pseudocode, using recursive function calls. You may not use any form of iteration. (5.0 marks) Question 3 (20 marks

Answer 1

Algorithm 1:

```

Function A1(root)

if root is null:

return 0

else:

left_height = A1(root.left)

right_height = A1(root.right)

return 1 + max(left_height, right_height)

End of function A1

```

Algorithm 2:

```

Function A2(root)

if root is null:

return -1

else:

return 1 + max(A2(root.left), A2(root.right))

End of function A2

```

Both algorithms aim to calculate the height of a binary tree. The height of a binary tree is defined as the number of edges on the longest path from the root to a leaf node.

Let's analyze the function call A2(root) for the given binary tree:

```

1

/ \

2 3

/ \ \

4 5 6

\

7

```

Applying Algorithm 2:

1. A2(1) is called. Since root is not null, we move to the else block.

2. A2(1) returns 1 + max(A2(2), A2(3)).

Now let's calculate A2(2):

1. A2(2) is called. Since root is not null, we move to the else block.

2. A2(2) returns 1 + max(A2(4), A2(5)).

Calculating A2(4):

1. A2(4) is called. Since root is not null, we move to the else block.

2. A2(4) returns 1 + max(A2(null), A2(null)).

Both A2(null) calls return -1.

Calculating A2(5):

1. A2(5) is called. Since root is not null, we move to the else block.

2. A2(5) returns 1 + max(A2(null), A2(7)).

A2(null) returns -1, and A2(7) is a leaf node (no children), so it returns -1 as well.

Returning to A2(2):

1. A2(2) returns 1 + max(1 + max(-1, -1), 1 + max(-1, -1)).

2. A2(2) returns 1 + max(1, 1).

3. A2(2) returns 1 + 1.

4. A2(2) returns 2.

Now let's calculate A2(3):

1. A2(3) is called. Since root is not null, we move to the else block.

2. A2(3) returns 1 + max(A2(null), A2(6)).

A2(null) returns -1, and A2(6) is a leaf node, so it returns -1 as well.

Returning to A2(1):

1. A2(1) returns 1 + max(2, 1).

2. A2(1) returns 1 + 2.

3. A2(1) returns 3.

Therefore, the function called A2(root) for the given binary tree returns 3.