UniqueTreeValues
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.
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
1. For the base case of a tree being null, what should be returned?
null
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.
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 ints values in the input tree.
2. 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);
a) What is the method header for help?
b) Why is the only line in create -- return help(values,0); why 0?
a) Public TreeNode help(int[] values, int index)
b) Our helper method completely builds the tree, there is nothing else we have to do. 0 here signifies that the root of the tree is at index 0, so we should start with index 0
2. For the base case of a leaf, what should be returned?
The leaf unmodified
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”]
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.
We want mySet to be sorted in order from least to greatest, so we use a TreeSet to make sure the elements are sorted.
2.
c) 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.
d) What is the base case, when will the parameters indicate a value of null is returned? Hint: when will value[index] generate an error?
c) The left and right subtrees are help(values, 2*index+1), help(values, 2*index + 2)
d) 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.
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.
3A. 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?
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;
}
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.
First, initialize mySet to be a new TreeSet<Integer>();
Then, pass mySet to a helper method modeled after inOrder (but replace 79 with adding to the set)
Finally, iterate through every value in the set using a for each loop and add them to a return array.
3. 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);
a) Conceptually, what is stored in the array?
b) How will you create the array nodes?
c) 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?
a) A list of single nodes whose values are the corresponding value in values.
b) Loop over the indices i in values and set nodes[i] = new TreeNode(values[i], null, null)
c) The parent of an index k is given by (k-1)/2, since even indices should be rounded down.
4. For a node that has one child, like 4 in the tree to the right or 18 in the tree above/left, 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)
3B. 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).
d) 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?
e) How is this like the heap used to implement a priority queue?
d) All odd indices are the left child of parents, and all even indices are the right child (so check if k % 2 == 0)
e) 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.
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.
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.