CS AP

Data Structure Exercise name____________________________

Binary Trees -- Solution

1. A binary tree is called a full tree if all its levels are completely filled with nodes. A full tree with h levels has 2^h ‑ 1 nodes. Write a method

public int fullTreeDepth(TreeNode root)

that checks whether a tree pointed to by root is a full tree, and if so returns the number of levels in that tree. If the tree is not a full tree, fullTreeDepth returns ‑1.

public int fullTreeDepth(TreeNode root)
 {
 if (root == null)
 return 0;
 int depth = fullTreeDepth(root.getLeft());
 if (depth < 0)
 return -1;
 if (fullTreeDepth(root.getRight()) != depth)
 return -1;
 return depth + 1;

}

2. Write a method

public TreeNode removeRightmostLeaf(TreeNode root)

that removes the rightmost leaf from a non-empty binary tree pointed to by root. The rightmost leaf is the leaf that is reached from the root of the tree by taking the right path whenever possible. If root is a leaf, this method returns null; otherwise it returns root.

public TreeNode removeRightmostLeaf(TreeNode root)
{
 if (root.getRight() != null)
  root.setRight(removeRightmostLeaf(root.getRight()));
 else if (root.getLeft() != null)
 root.setLeft(removeRightmostLeaf(root.getLeft()));
 else
 root = null;
 return root;
}

3. Write a method (on the back)

public TreeMap combine(Map map1, Map map2)

that combines map1 and map2 into a new map. combine should work as follows: first each pair (key, value) from map1 is added to the resulting map; second, each (key, value) pair from map2, such that key is not in the set of keys for map1, is added to the resulting map.

public TreeMap combine(Map map1, Map map2)
{
 TreeMap resultMap = new TreeMap();
 Iterator iter;
 Object key;
 
 iter = map1.keySet().iterator();
 while (iter.hasNext())
 {
 key = iter.next();
 resultMap.put(key, map1.get(key));
 }
 
 iter = map2.keySet().iterator();
 while (iter.hasNext())
 {
 key = iter.next();
 if (!resultMap.containsKey(key))
 resultMap.put(key, map2.get(key));
 }
 return resultMap;

}