CompSci 100e, Inclass List & Tree Exercises & Prelab 13

Name: ___________________
Collaborators & Resources Used:
Use the definition of ListNode below for a doubly linked list of strings. Assume that lists do NOT have header nodes. public class ListNode { String info; ListNode prev; ListNode next; ListNode(String s, ListNode before, ListNode after){ info = s; prev = before; next = after; } } Use the following definition for a TreeNode with a parent pointer. public class TreeNode { String info; TreeNode left; TreeNode right; TreeNode parent; TreeNode (String s, TreeNode lt, TreeNode rt, TreeNode p) { info = s; left = lt; right = rt; parent = p; } }
  1. Write a method maxNode that returns a reference to the node whose info field is alphabetically last in the unsorted linked list. Your solution should be iterative. /** * returns the node whose info field is largest (alphabetically), * returns 0 if list is NULL */ public static Node maxNode (ListNode list) { }
  2.  Write the method maxNode that returns a reference to the node whose info field is alphabetically last in the unsorted linked list. Your solution should be recursive. /** * returns the node whose info field is largest (alphabetically), * returns 0 if list is NULL */ public static Node maxNode (ListNode list) { }
  3. Write the function below which finds a node in a doubly-linked list, unlinks it, and moves it to the front of the list. For example, if list is (a,b,c,d) as shown. 
                +---+   +---+   +---+   +---+
   list---> |   |-->|   |-->|   |-->|   |->|||
            | A |   | B |   | C |   | D |
      |||<--|   |<--|   |<--|   |<--|   }
            +---+   +---+   +---+   +---+
    Then after the call list = moveToFront(list,"C") the picture should be: 
                +---+   +---+   +---+   +---+
   list---> |   |-->|   |-->|   |-->|   |->|||
            | C |   | A |   | B |   | D |
      |||<--|   |<--|   |<--|   |<--|   }
            +---+   +---+   +---+   +---+
    Be sure to unlink/relink all next/prev pointers, but be careful about special cases like moving the first or last nodes of the list. /** * Move node containing word to front of list and * return modified list. If word not found, no changes * made to list, original list returned * @param list is list being modified * @param word is targetted node for move-to-font * @return first node in possibly modified list. */ public ListNode moveToFront(ListNode list, String word) { Node first = list;
  4. Tree to List Recursion Problem

    Thanks to Nick Parlante for this problem.

    In a binary search tree, each node contains a single data element and "small" and "large" pointers to sub-trees (i.e. left and right). A binary tree may be defined as follows: Below is a binary search tree with the numbers 1 through 5.

    Now, consider the data as a circular doubly linked list.

    The challenge is to take an ordered binary tree and rearrange the internal pointers to make a circular doubly linked list out of it. The left pointer should play the role of prev and the right pointer should play the role of next. The list should be arranged so that the nodes are in increasing order.

    1. Given the following definition of the class TreeList. Fill in the blank methods. public class TLNode { int data; TLNode left; TLNode right; TLNode (int v, TLNode lt, TLNode rt) { data = v; left = lt; right = rt; } /* helper function -- given two list nodes, join them together so the second immediately follow the first. Sets the .next of the first and the .prev of the second. */ public static void join(TLNode a, TLNode b) { } /* helper function -- given two circular doubly linked lists, append them and return the new list. */ public static TLNode append(TLNode a, TLNode b) { }
    2. Write a recursive methof treeToList(TLNode root) that takes an ordered binary tree and rearranges the internal pointers to make a circular doubly linked list out of the tree nodes. The prev pointers should be stored in the left field and the next pointers should be stored in the right field. The list should be arranged so that the nodes are in increasing order. Return the head pointer to the new list. The operation can be done in O(n) time -- essentially operating on each node once. public static TLNode treeToList(TLNode root) {

     

     

  5. Write the method hasPathSum whose header is given below. hasPathSum returns true if there exists some root-to-leaf path in the tree whose root is t whose nodes sum to target and returns false otherwise.

    For example, in the tree shown below there are exactly four root-to-leaf paths. The sums of the paths are 27, 22, 26, and 18. Thus the value of hasPathSum(t,27) should be true and the value of hasPathSum(t,30) should be false (assuming t points to the root of the tree --- the node whose info field has value 5.)

    *

    Hint: You should make two recursive calls, you must decide on the value of target for each recursive call so that you can use the return values of the recursive calls to solve the problem. Note: in a tree with one node (a leaf) you can determine immediately if there's a path that sums to the target based on whether the target and the node are equal.

    /** * Return true if and only if t has a root-to-leaf path * that sums to target. * @param t is a binary tree * @param target is the value whose sum is searched for on some * root-to-leaf path * @return true if and only if t has a root-to-leaf path summing to target */ public static boolean hasPathSum(TreeNode t, int target) { }
  6. You're to analyze the code in the method findKthInOrder whose header is given below. Given an integer k and a binary search tree with unique values, findKthInOrder returns a reference/pointer to the node that contains the kth element if the elements are in sorted order --- the smallest value is k == 1, the second smallest is k == 2, and so on.

    For example, in the tree t shown below (t points to the root), findKthInOrder(t,4) returns a reference/pointer to the node with value 9, findKthInOrder(t,8) returns a reference/pointer to the node with value 18, and findKthInOrder(t,12) returns null since there are only 9 nodes in the tree.

    *

    The method count discussed in lecture returns the number of nodes in a tree.

    /** * Returns number of nodes in t. * @param t is the tree whose nodes are counted * @return number of nodes in t */ public static int count(TreeNode t) { if (t == 0) return 0; return 1 + count(t.left) + count(t.right); } /** * Returns reference to k-th node when values considered * in sorted order, return null if t has fewer than k nodes * @param t is a binary search tree * @param k specifies which value in t to return * @return k-th value when nodes considered in order */ public static TreeNode findKthInOrder(TreeNode t, int k) { if (t == null) return null; // can't find anything, empty int numLeft = count(t.left); if (numLeft + 1 == k) { // current node return t; } else if (numLeft >= k) { // in left subtree return findKthInOrder(t.left, k); } else { return findKthInOrder(t.right, k - (numLeft + 1)); } }
  7. Assuming trees are roughly balanced (e.g., average case), write a recurrence for findKthInOrder and give the solution to the recurrence.
  8. Write a recurrence for findKthInOrder for the worst case, i.e., when a tree is completely unbalanced and the method is called to do the most work on every recursive call. What is the solution to this recurrence?