Java Reference
In-Depth Information
The else case involves a root node with left and right subtrees. How many leaf
nodes are in such a tree? Think about what recursive calls on the left and right sub-
trees will return. They will tell you how many leaves are in the subtrees. Each of
those leaves is a leaf of the overall tree, so you might think that the answer is as simple
as returning the sum of the subtree leaves:
private int countLeaves(IntTreeNode root) {
if (root == null) {
return 0;
} else {
return countLeaves(root.left) + countLeaves(root.right);
}
}
If you were to test this version of the code, you'd find that it always returns 0 as
the number of leaves in a tree. That's because you forgot one important case.
When you have a root node that has left and right subtrees, the number of leaves
in that tree is generally the sum of the number of leaves in the two subtrees,
except in one important case. What if the subtrees are both empty? That would
mean that the node you are looking at is itself a leaf node. That particular tree has
exactly one leaf node (the root). You have to introduce a special case that handles
that particular situation:
private int countLeaves(IntTreeNode root) {
if (root == null) {
return 0;
} else if (root.left == null && root.right == null) {
return 1;
} else {
return countLeaves(root.left) + countLeaves(root.right);
}
}
It may seem odd, but that simple change makes this code work. Each leaf node
returns an answer of 1, and those answers are added together by the other calls to
produce a count of the various leaf nodes in the tree.
17.4 Binary Search Trees
In this section we will study a particularly useful kind of binary tree known as a
binary search tree . Recall from Chapter 13 that we can efficiently search through a
sorted array using the binary search algorithm. That algorithm is highly efficient
 
Search WWH ::




Custom Search