# 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&#x20;

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.

{% hint style="info" %}
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.&#x20;

What does this look like to you?
{% endhint %}

### Part 2&#x20;

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

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.&#x20;

## Exercise 2 - Implementing a Binary Tree

### Part 1&#x20;

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&#x20;

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

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

### Part 3&#x20;

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

```cpp
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&#x20;

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

Demonstrate the usage by creating a binary search tree of floats.&#x20;
