Binary Trees - Building Java Programs: A Back to Basics Approach - page 1029

16. Write a method called trim that accepts minimum and maximum integers as parameters and removes from the tree
any elements that are not within that range inclusive. For this method you should assume that your tree is a binary
search tree and that its elements are in valid binary search tree order. Your method should maintain the binary search
tree ordering property of the tree. This property is important for solving this problem.

17. Write a method called tighten that eliminates branch nodes that have only one child. Each such node should be
replaced by its only child. (This can lead to multiple replacements because the child might itself be replaced.) For
example, if a variable called t refers to reference tree #2, the call of t.tighten(); should leave t storing the fol-
lowing tree.

2

0 1

4 9

18. Write a method called combineWith that accepts another binary tree of integers as a parameter and combines
the two trees into a new third tree that is returned. The new tree's structure should be a union of the structures of
the two original trees; it should have a node in any location where there was a node in either of the original trees
(or both). The nodes of the new tree should store an integer indicating which of the original trees had a node at
that position ( 1 if just the first tree had the node, 2 if just the second tree had the node, and 3 if both trees had the
node). Your method should not change the structure or contents of either of the two original trees that are being
combined.

For example, suppose IntTree variables t2 and t3 refer to reference trees #2 and #3 respectively. The call of
t2.combineWith(t3) will return a reference to the following new tree. Keep in mind that nodes numbered 1 are
those that appear only in t2 , nodes numbered 2 appear only in t3 , and nodes numbered 3 appear in both.

3

3 3

3 2 1 1

1 1

19. Write a method called inOrderList that returns a list containing the sequence of values obtained from an
inorder traversal of your binary tree of integers. For example, if a variable t refers to reference tree #3, then the call
t.inOrderList() should return the list [8, 3, 7, 2, 1] . If the tree is empty, your method should return an
empty list.