Problem $3(24$ marks$)$

Consider the following binary tree made up of both positive and negative integers.

Our problem is to find the maximum possible sum from one leaf to another in a binary tree. In the example above, the maximum sum is $27$ which starts at leaf node $3$ and ends at leaf node $10,$ that is$,$

$3+6+9+0-1+10=27$

a$)(6$ marks$)$ Outline an algorithm that finds the maximum sum between two leaf nodes using a single traversal of the binary tree.

b$)$ Implement $(10$ marks$)$ and test $(4$ marks$)$ your algorithm in part a$).$ You may wish to store additional information in each node.

c$)(4$ marks$)$ Augment your code in part b$)$ to return the actual values along the maximum$-$sum path between the two leaf nodes.

Page $2$ of $3$

Problem $4(17$ marks$)$

Using the AVL implementation on Blackboard as a base, re$-$implement $(12$ marks$)$ and test $(5$ marks$)$ the Remove method to avoid re$-$traversing the tree $($as discussed in class$).$