UniqueTreeValues
TreeBuilder I
TreeBuilder II
TreeTighten
LeafCollector
100
1. If a binary tree is a search tree, in what order are the nodes of the tree visited using an inOrder traversal?
They’re in sorted order from least to greatest.
100
2a. Suppose I suggest a helper method with two parameters: the int[] array and an index into that array. The helper method will create and return a tree whose root is given by the index. The only line in the required method create is return help(values,0);
What is the method header for help?
private TreeNode help(int[] values, int index)
100
2b. Suppose I suggest a helper method with two parameters: the int[] array and an index into that array. The helper method will create and return a tree whose root is given by the index. The only line in the required method create is return help(values,0);
Why is the only line in create -- return help(values,0); why 0?
The helper method completely builds the tree; there is nothing else we have to do before/after. 0 here signifies that the root of the tree is at index 0, so we should start with index 0
100
1. For the base case of a tree being null, what should be returned?
null
100
2. If the problem asked to visit right children before left (instead of left before right). What would the return array be?
It would be [“15 10 6”, “12 4”, “8”]
200
2. If line 79 above is replaced by: mySet.add(root.info); where mySet is an instance variable of type Set<Integer>, describe the contents of mySet after all nodes have been visited.
mySet will be a set of all of the unique int values in the input tree
200
3a. Consider a non-recursive version where the first step is to create an array of TreeNode values, e.g., TreeNode[] nodes = new TreeNode[values.length]; You'll create this array so that nodes[k] = TreeNode(values[k],null,null);
Conceptually, what is stored in the array?
The array contains single nodes whose values are the corresponding value in the values array
200
3b. Consider a non-recursive version where the first step is to create an array of TreeNode values, e.g., TreeNode[] nodes = new TreeNode[values.length]; You'll create this array so that nodes[k] = TreeNode(values[k],null,null);
How will you create the array nodes?
Loop over the indices i in values and set nodes[i] = new TreeNode(values[i], null, null)
200
2. For the base case of a leaf, what should be returned?
The leaf
200
1. Explain in your group why the array returned for the tree shown here is ["6 10 15", "4 12", "8"] as part of demonstrating your understanding of the problem.
The leaves in the original tree are 6,10, and 15, so these are removed in the first round. 4 and 12 are then the leaves in the second round, and then we are left with just the root 8 and it is removed last.
300
3. For this APT, in which the tree is not a search tree, explain why a TreeSet is an appropriate type for the instance variable mySet in the previous question.
mySet should be sorted in order from least to greatest, so we use a TreeSet to keep the elements sorted
300
1. What tree (draw it) is returned for the array {2,4,6,8,10}; Note that the pre-order apt-style string for this tree is {2,4,8,x,x,10,x,x, 6,x,x}. Why is that the string?
2
/ \
4 6
/ \
8 10
300
2d. Suppose I suggest a helper method with two parameters: the int[] array and an index into that array. The helper method will create and return a tree whose root is given by the index. The only line in the required method create is return help(values,0);
What is the base case, when will the parameters indicate a value of null is returned? Hint: when will value[index] generate an error?
We should return null if index is ever out of bounds of the values array, since this means that 2*index extended beyond the end of the array.
300
3. What tree should be returned for the call tighten(tree) if tree points at the root 8 of the diagrammed tree
It should be this tree with the node 4 removed and the node 6 taking the spot of 4.
300
2a. Consider a helper method with this method signature, that removes all the leaves from a tree and returns them in the List parameter.
private void collectAndRemove(TreeNode root, List<String> list)
This method will only be called when the parameter root is not a leaf. One line of code in the method is shown below
Explain how this code effectively removes a leaf node from the tree. What is the similar code that will remove a leaf that is to the right of root?
(must explain how this code works AND what the code for the right leaf would be)
This code checks if the left subtree is a leaf and adds it to the list associated with this round. It then sets the left subtree to null, which effectively removes it in preparation for the next round.
The similar code for a leaf to the right is:
If (isLeaf(root.right)) {
list.add(“”+root.right.info);
root.right = null;
}
400
3c. Consider a non-recursive version where the first step is to create an array of TreeNode values, e.g., TreeNode[] nodes = new TreeNode[values.length]; You'll create this array so that nodes[k] = TreeNode(values[k],null,null);
The root of the tree to return is nodes[0]. If you write a loop that uses all valid indexes 1,2,3, …, e.g., for(int k=1; k < values.length; k++) how will you calculate the parent of the node whose index is k? Hint: k/2 will not work, e.g., the children of index 0 are 1 and 2, but 2/2 == 1. Hint: what about (k-1)/2?
The parent of an index k is given by (k-1)/2, since even indices should be rounded down.
400
3d. Consider a non-recursive version where the first step is to create an array of TreeNode values, e.g., TreeNode[] nodes = new TreeNode[values.length]; You'll create this array so that nodes[k] = TreeNode(values[k],null,null);
In this k=1,2,... loop how do you determine whether the parent's left or right child is the TreeNode stored in nodes[k]? Hint: the parent of 3 has index 1 and the parent of 4 has index 1 which is the left child of 1?
All odd indices are the left child of parents, and all even indices are the right child (so check if k % 2 == 0)
400
4. For a node that has one child, like 4 in the tree in #3 or 18 in the tree below, what recursive call provides the value to return? Note that 4 has a null left-child and 18 has a null right child.
If the left child is the null node, we return tighten(t.right)
If the right child is the null node, we return tighten(t.left)
400
3b. Consider a helper method with this method signature, that removes all the leaves from a tree and returns them in the List parameter.
private void collectAndRemove(TreeNode root, List<String> list)
This method will only be called when the parameter root is not a leaf. One line of code in the method is shown below
If the node to the left of root is not a leaf, that is it's either null or a subtree, what should the code do? (hint: think recursively)
If the node to the left is not a leaf, the code should recursively call collectAndRemove to add all of the leaves in the children of the left node i.e. it should call collectAndRemove(root.left, list).
500
4. Explain how the APT method unique can initialize variable mySet and call a helper method modeled after the modified inOrder above -- then use the values in mySet to create a return array.
1. Initialize mySet to be a new TreeSet<Integer>();
2. Pass mySet to a helper method modeled after inOrder (but replace 79 with adding to the set)
3. Iterate through every value in the set using a for each loop, add them to a return array.
500
3e. Consider a non-recursive version where the first step is to create an array of TreeNode values, e.g., TreeNode[] nodes = new TreeNode[values.length]; You'll create this array so that nodes[k] = TreeNode(values[k],null,null);
How is this like the heap used to implement a priority queue?
This is exactly the structure of a heap used to maintain a priority queue, where the order in the queue based on the tree is given by left subtree index = 2*index + 1 and right subtree index = 2*index + 2.
500
2c. The base case will return null; a non-base case will return a TreeNode whose info field is value[index]. What are the values of this node's left and right subtrees? Hint: think recursively.
The left and right subtrees are help(values, 2*index+1), help(values, 2*index + 2)
500
5. If both children are non-null, explain why this code returns a correctly tightened tree (conceptually)
If we know the root has two non-null children, then we know we don’t need to do anything to tighten the root's connection to its two children. So, if we successfully can tighten the left and right subtrees, the whole tree will be fully tightened.
500
4. The helper method shown above will be called from the required APT method getLeaves. The method implements what's called a round in the APT. Conceptually, when will the rounds be over? What property of root will hold when it's no longer necessary to call collectAndRemove?
The rounds will be over when the tree is null. Once the root itself is a leaf, we do not need to call collectAndRemove and can just add the root as the final round and return the result.