Section 22

Binary trees
Implementing an iterator for a binary tree
Balanced search trees

Binary trees

This is the binary tree from Tuesday’s section

What will the tree look like after deleting 6, 15, and 20 (in that order)? ¹
Is the resulting tree (the tree after the deletions) balanced? ²

Recall from lecture that a node in a binary tree with empty left and right subtrees is called a leaf node. For the following exercises, use the following basic TreeNode class representing a node in a binary tree.

public class TreeNode {
    private int data;
    private TreeNode left;
    private TreeNode right;


    public TreeNode(TreeNode left, TreeNode right){
        this.data = 0;
        this.left = left;
        this.right = right;
    }
}

Write a static method numNodes that counts the number of nodes in any tree of TreeNode objects. ³
Write a static method numLeaves that counts the number of leaf nodes in any tree of TreeNode objects. ⁴

Implementing an iterator for a binary tree

In your next problem set, you will implement an iterator for the LinkedTree class from the lecture notes.

Find the alternate version of LinkedTree from your problem set starter files that contains the PreorderIterator class, defined as an inner class.

You will also need the LinkedTreeIterator interface, which you should not modify, and the LLQueue class and associated Queue interface (a queue is used by the class to perform a level-order traversal).

Find the definition of the Node class on line 20. Note that this definition contains three references to other nodes in the tree: a node’s left child, right child, and parent node. We made this alteration so that our iterator could traverse the tree to a leaf and be able to make its way back to unvisited nodes. ⁵
Find the preorderIterator() method on line 321. This method creates and returns a new PreorderIterator object. This PreorderIterator object implements the LinkedTreeIterator interface, which only specifies two methods: hasNext() and next(). ⁶
Find the PreorderIterator class definition on line 333. Notice that the iterator keeps a single reference nextNode to a node the integer data part of which will be returned by the iterator when the next() method is called. ⁷
Perform a trace of the next() method. Start with the following binary search tree. ⁸

Balanced search trees

Insert the following sequence of keys into an empty 2-3 tree: ⁹
```
15, 23, 20, 10, 13, 6, 18, 35, 27, 9
```

Here are the tree diagrams:

The tree after deleting 6.

The tree after deleting 15. We took the node with the smallest key in 15’s right subtree for replacement. We could have also chosen the largest key value in 15’s left subtree.

The tree after deleting 20.

↩
No. ↩

The complete code can be found in TreeNode.java, however I’ve included the numNodes() method below:

public static int numNodes(TreeNode n) {
    if (n == null)
        return 0;

    return 1 + numNodes(n.left) + numNodes(n.right);
}

↩

Find the complete code in TreeNode.java. The numLeaves() method is included below:

public static int numLeaves(TreeNode n) {
    if (n == null)
        return 0;

    if (n.left == null && n.right == null)
        return 1;

    return numLeaves(n.left) + numLeaves(n.right);
}

↩

Note that the inner Node class is private, which effectively hides the notion of a Node from any client code. This necessitates a way to present clients with the contents of a Node without returning any references of type Node. Hence the iterator, and LinkedTreeIterator interface. ↩
Note that the LinkedTreeIterator returns an integer, which corresponds to the key of a Node object. ↩
This PreorderIterator class is also private. This is an interesting point, since the preorderIterator() method has a return type of LinkedTreeIterator. Therefore no client code will ever know the details of a PreroderIterator object — it is only guaranteed that some object that implements the interface will be returned. However, we know that this iterator will give client code access to the keys in the tree in a preorder fashion. ↩
We won’t reproduce an entire trace here, but we will reiterate (ha) what was said in general. The next() method’s while loop condition cannot simply be parent != null && parent.right == null, since this could cause the next() method to stop traversing the tree such that parent refers to a node whose right child we have already reached. Thus we must make sure we are not choosing a parent node along the path we’ve historically taken to where we started (where nextNode currently is). ↩
Here’s the final 2-3 tree:

*Note: The Node containing 25 in this image should actually contain 35. ↩

Last updated on July 31, 2025.