Recitation 8:
Trees II

October 26, 2012

 

Snarf the recitation 8 code.

Part 1: Worst vs. Average

We discussed in class that when building a tree, the worst case would be when adding nodes that are already sorted. Run the snarfed code and plot the number of nodes compared to the height of the tree.

Modify your code to build trees using a list of random numbers instead of ordered numbers. Create a new plot of the number of nodes compared to the height of the tree when using a random list of numbers.

Discuss, (using big-O) the difference between the two approaches. Add your discussion and graphs to a recitation8.pdf file.

Part 2: Coding

Part A: hasPathSum

Write the method hasPathSum whose header is given below. Method 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.)



No this is not a picture of a binary search tree, but it is a binary tree. Your code uses binary search trees, however the implementation for this method is the same.

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. So identification of a leaf-node will likely be a base case in your recursive method.

public boolean hasPathSum(int target) {
    return hasPathSum(root, target);
}
/**
* 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
*/
private boolean hasPathSum(IntTreeNode current, int target) {




}

Part B: findK

Write a method to return the value in the kth element in the tree, assuming elements are ordered following an in-order traversal. From the tree above, an in-order traversal orders the nodes as follows: 7 - 11 - 2 - 4 - 5 - 13 - 8 - 4 - 1 where 7 is the 1st element in the tree, 11 is the 2nd element, etc.. For an ordered tree, the nodes will be in numerical order.

A naive approach to finding the kth element in a tree would use an in-order traversal and return the kth element. However, this is in linear time and binary search trees should be able to access an element in O(treeHeight). In Compsci201 we care about efficiency so you will need to wirte the method in O(treeHeight).

Hint: Modify your Node inner class to save the size of the subtree. That is, from the tree above, 5 would have a subtree size of 9, 4 would have a subtree size of 4, and 8 would have a subtree size of 4. Node 5 is the 5th node in the tree. This is one more than the size of its left subtree. You will need to check if the kth node is to the left or right of the current node you are on. You should then recurse on the appropriate subtree. Drawing pictures also helps.

public int findK(int k) {
    return findK(root, k);
}

private int findK(IntTreeNode current, int k) {


}

Submit

Submit your recitation8.pdf from part1 and your TreeNodeExample.java file with your completed code for hasPathSum and findK to the recitation 8 folder by 11:59pm on Sunday, October 28.