Consider a binary tree T with n nodes. We define the diameter of the tree T to be longest between any two nodes of the tree. The distance between two nodes in a tree is simply the number of edges in the unique path connecting those two nodes. An example tree is shown below, with 6, the distance between nodes 10 and 12. Describe an efficient algorithm for computing the diameter of a given binary tree. Describe the high level idea of your algorithm and also give a detailed description of your algorithm in pseudocode. You must make your algorithm as efficient as possible for full marks. You may assume that you are given a reference to the root of the tree, and that nodes have left, right and parent references. Explain the running time of your algorithm using big Oh notation. You must give the worst case running time and also explain why this is the worst case bound for your solution/pseudocode. Show two intermediary stages of building the AVL tree, after inserting 3, the final AVL tree after inserting 1. Use Dijkstra's algorithm to determine the shortest path from node A (or vertex) to each other node. As you progress through the algorithm, update the following table with both the shortest distance so far from node A (column 2) and the predecessor node (column 3) as we did in lectures, crossing out the distances as smaller ones are found; and (ii) list the nodes in the order that they are added to the cloud of nodes