Section 21

Binary trees
Bug of the Day
Binary tree traversals
Huffman trees
Binary search trees

Binary trees

For the following binary tree exercises, refer to the binary tree below.

What are the ancestors of node D? ¹
What are the descendants of node G? ²
What is the depth of node A? ³
What is the height of this tree? ⁴

Bug of the Day

Consider the following variation of the LinkedTree class’ insert() method, which is supposed to associate a new data item with the specified integer key key:

public void insert(int key, Object item) {
    if (root == null) {
        root = new Node(key, item);
        return;
    }

    Node trav = root;
    while (trav != null) {
        if (trav.key == key) {
            trav.data.addItem(item, 0);
            return;
        }

        if (key < trav.key)
            trav = trav.left;
        else
            trav = trav.right;
    }

    Node newNode = new Node(key, data);
    trav = newNode;
}

Determine what is wrong with this variation of the insert method and then examine the correct insert method in the LinkedTree.java file.

Binary tree traversals

For the following binary tree exercises, refer to the binary tree below.

Perform a pre-order traversal of this tree, writing down the letter of a node as you mark it as visited. ⁵
Perform an in order traversal of this tree, writing down the letter of a node as you mark it as visited. ⁶
Perform an post-order traversal of this tree, writing down the letter of a node as you mark it as visited. ⁷

Huffman trees

You are given a document in which all characters are drawn from a set of six possible characters, the frequencies of which have been determined by analysis of the document. The possible characters and associated frequencies have been included below.

Character	Frequency
e	45
a	33
r	20
i	18
n	15
d	10

Create a Huffman tree for this document. ⁸
Use the Huffman tree to decode the following sequence of bits from a compressed document. ⁹
```
00101000100101
```

Binary search trees

Recall from lecture that a binary search tree is a type of binary tree in which the nodes in the tree are ordered by a key. A binary tree is said to be a binary search tree if the following property, the binary search tree property, holds:

A binary search tree is either an empty tree, or a node with key k, whose left subtree contains keys less than k, and whose right subtree contains keys greater than or equal to k.

Insert the following sequence of keys into an empty binary search tree. ¹⁰
```
15, 23, 20, 10, 13, 6, 18, 35, 23 (a duplicate), 9, 24
```

We say that a tree is balanced when, for each node, the node’s subtrees have the same height or have heights that differ by at most one.

Is the resulting tree from the insertions above balanced? ¹¹

Recall the process of deletion from a binary search tree. It is more complex than deletion from a simple binary tree, since any deletion must preserve the binary search tree property.

B and F. ↩
I and H. ↩
2. ↩
3; the height of a tree is the maximum depth of any node. ↩
F, B, A, D, C, E, G, I, and H. ↩
A, B, C, D, E, F, G, H, and I. ↩
A, C, E, D, B, H, I, G and F. ↩
Here’s a step-by-step trace of creating the tree:

Step 1: initial sorted configuration

Step 2: d and n nodes coalesce

Step 3: i and r nodes coalesce

Step 4: a node and tree containing d and n coalesce

Step 5: e node and tree containing i and r coalesce

Step 5: subtrees coalesce

↩
Assuming that going left on the tree corresponds to 0 and going right corresponds to 1, the binary string decodes to the word nadir. ↩
Here’s the tree after all insertions. We stored the data part of the duplicated 23 key in the existing node. We could have also inserted the duplicate key as a new node.

↩
If we decided to store the data part of the duplicated 23 key in the existing node (as we did in the diagram above), the tree is balanced. However, if we inserted 23 to the left of 35, inserting 24 would cause the tree to be unbalanced. ↩

Last updated on July 28, 2026.