Solutions to other chapters:
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26  
Java Methods Home Page Skylight Publishing



Java Methods A & AB:
Object-Oriented Programming and Data Structures

Answers and Solutions to Exercises

Chapter 23

2.   [log2 100000] + 1 = log2 131072 = 17
4.   Base case: For h = 0 the number of nodes in the tree is 0 and 0 = 20-1. Likewise, for h = 1 the number of nodes in the tree is 1 and 1 = 21-1.

Suppose the statement is true for any h < n. Take a tree with n levels. From the inductive hypothesis, the numbers of nodes in its left and right subtrees do not exceed 2n-1 - 1. Therefore, the total number of nodes for the tree does not exceed

    (2n-1 - 1) + (2n-1 - 1) + 1 = 2n - 1

QED.

6.   public boolean isLeaf(TreeNode node) { return node != null && node.getLeft() == null && node.getRight() == null; }
8.   Leaves.
10.   public int depth(TreeNode root) { if (root == null) return -1; return 1 + Math.max(depth(root.getLeft()), depth(root.getRight())); }
12. (a) public TreeNode copy(TreeNode root) { if (root == null) return null; return new TreeNode(root.getValue(), copy(root.getLeft()), copy(root.getRight())); }
15. (a) -:- / \ 2 + / \ -:- -:- / \ / \ 1 x 1 y
(g) Inorder, preorder, and postorder traversals of a binary tree visit its leaves in the same sequence. You can use mathematical induction (over the total number of nodes) to prove this fact: apply the induction hypothesis to the left and the right subtrees.
16. (b) T
(c) F -- the tree may have degenerated into a near linear shape
18.   475 557 / \ / \ 474 749 474 681 / / / \ / \ 292 623 292 475 623 749 / \ 557 681
19.   L / \ G O / \ / \ A I M R / \ H T
Inorder: A G H I L M O R T   Preorder: L G A I H O M R T
Postorder: A H I G M T R O L
22.   public TreeNode maxNode(TreeNode root) { if (root == null) return null; TreeNode node = root; while (node.getRight() != null) node = node.getRight(); return node; }

Copyright © 2006 by Skylight Publishing