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

d.

m

g q

b k x

e

e.

7.2

1.9 9.6

8.1 21.3

16. What will be true about the results of an inorder traversal of a binary search tree?

For each of the next four problems, draw the binary search tree that would result if the given elements were added to
an empty binary search tree in the given order. Then write the elements of the tree in the order that they would be
visited by each kind of traversal (preorder, inorder, and postorder).

17. Leia, Boba, Darth, R2D2, Han, Luke, Chewy, Jabba

18. Meg, Stewie, Peter, Joe, Lois, Brian, Quagmire, Cleveland

19. Kirk, Spock, Scotty, McCoy, Chekov, Uhuru, Sulu, Khaaaan!

20. Lisa, Bart, Marge, Homer, Maggie, Flanders, Smithers, Milhouse

21. Why does the add method of a binary search tree need to return the newly added/created node?

22. What is the x = change(x) pattern, and how is it used with binary trees?

23. How many nodes at most would be examined in a call to contains on a perfect binary search tree of height N ?

24. Consider the following implementation of the contains method. How does it differ from the one we showed in
Section 17.4? Is it better or worse, and why?

private boolean contains(IntTreeNode root, int value) {
if (root == null) {
return false;
} else if (value == root.data) {
return true;
} else {
return contains(root.left, value) || contains(root.right, value);

}

}