Programming Lab 8 : Trees

CSCI-UA 9102, Data Structures

- Exercise 8.1. Let T be a binary tree with n positions that is realized with an array representation A, and let f() be the level numbering function of the positions of T. Give the implementation of the each of the methods root, parent, left, right, isExternal, and isRoot

- Exercise 8.2. The path length of a Tree T is the sum of the depths of all positions in T. Give a linear time method for computing the path length of tree T

- Exercise 8.3. Two ordered trees T’ and T” are said to be isomorphic if one of the following conditions hold: (1) both T’ and T” are empty; (2) Both T’ and T” consist of a single node; or (3) The roots of T’ and T” have the same number k>=1 of subtrees and the ith such subtree of T’ is isomorphic to the ith subtree of T” for i=1,…, k

- Exercise 8.4. Give an efficient algorithm that computes and prints for every position p of a tree T, the elements of T followed by the height of p’s subtree

- Exercise 8.5. Add support in LinkedBinaryTree for a method ‘pruneSubtree(p)’ that removes the entire subtree rooted at position p, making sure to maintain an accurate count of the size of the tree. What is the running time of your implementation?

- Exercise 8.6. Add support in LinkedBinaryTree for a method swap(p,q) that has the effect of restructuring the tree so that the node referenced by p takes the place of the node referenced by q, and vice versa. Make sure to properly handle the case where the nodes are adjacent.

- Exercise 8.7.
Design algorithms for the following operations for a binary tree T:
- preorderNext(p): Return the position visited after p in a preorder traversal of T (or null if p is the last node visited)
- inorderNext(p): Return the position visited after p in an inorder traversal of T (or null if p is the last node visited)
- postorderNext(p): Return the position visited after p in a postorder traversal of T (or null if p is the last node visited)

- Exercise 8.8. Let T be a tree with n positions. Define the lowest common ancestor (LCA) between two positions p and q as the lowest position in T that has both p and q as descendants (where we allow a position to be a descendant of itself). Given two positions p and q, describe an efficient algorithm for finding the LCA of p and q. What is the running time of your algorithm?

- Exercise 8.9. Let T be a binary tree with n positions, and, for any position p in T, let dp denote the depth of p in T. The distance between two positions p and q is dp+dq-2da where a is the lowest common ancestor (LCA) of p and q. The diameter of T is the maximum distance between two positions in T. Give an efficient algorithm for finding the diameter of T. What is the running time of your algorithm.

- Exercise 8.10. Implement the binary tree ADT using the array based representation.

- Exercise 8.11*. write a program that takes as input a general tree T and a position p of T and converts T to another tree with the same set of position adjacencies, but now with p as its root.

- Exercise 8.12. Implement the tree ADT using a linked structure. Provide a reasonable set of update methods for your tree.

- Exercise 8.13. Let T be a binary tree with n positions. Define a Roman position to be a position p in T such that the number of descendants in p’s left subtree differ from the number of descendants in p’s right subtree by at most 5. Provide a linear time method for finding each position p of T, such that p is not a Roman position, but all of p’s descendants are Roman.

- Exercise 8.14. Given a binary tree, it is possible to represent it on the terminal as shown below. Build a simple (p-level) tree and write down the method that represent the tree.

```
2
/ \
/ \
/ \
/ \
7 5
/ \ / \
/ \ / \
2 6 3 6
/ \ / \ / \ / \
5 8 4 5 8 4 5 8
```