Chapter 19 - Worked Exercises 2

Exercise 1 - Binary Tree

Part 0

1. What is a binary tree?

2. What is a binary search tree?

3. Which C++ container is internally represented by a binary search tree?

Part 1

Draw a binary tree of integers, starting first with an empty tree, then adding elements:

5, 20, 6, 10, 1, 4, 3

in this specific order.

Bonus: Draw a binary tree of integers, starting with an empty tree, then adding the elements:

5, 10, 15, 20, 25

in this specific order.

What does this look like to you?

Part 2

Explain the characteristics of a binary tree that allows faster search operations than would otherwise be possible with a sequential container like std::vector.

Show an example of a binary tree being able to performs lookups in fewer operations when compared to an std::vector with the same elements.

Exercise 2 - Implementing a Binary Tree

Part 1

Based on your understanding of a Node in a binary tree, and the values that it is required to store, define the Node class for a binary tree of integers.

Part 2

Implement a function for inserting a new integer value into a binary tree starting from its root:

void insert(Node*& root, int value);

Part 3

Implement a function for looking up an integer value in a binary tree starting from its root:

bool search(Node* root, int value);

The function should return true if the value was found in the binary tree, and false otherwise.

Part 4

Convert all definitions in Parts 1-3 into template classes and functions to be able to store values of any type.

Demonstrate the usage by creating a binary search tree of floats.