Trees

Question 1

What is a tree?

Answer 1

A tree is a connected, undirected graph with no cycles.

Question 2

What is a characteristic that not all trees have?

Answer 2

Not all trees have roots!

Question 3

What is a rooted tree?

Answer 3

A tree where one node has been designated as the root.

Question 4

What is a binary tree?

Answer 4

A rooted tree where each parent node has at most two child nodes.

Question 5

What is a binary search tree?

Answer 5

An ordered binary tree.

Question 6

Which item in a line of items is the root?

Answer 6

The first item that is entered is always the root!

Question 7

Searching for an item in a binary search tree.

Answer 7

Just like a binary search, searching for an item in a binary tree is an O(logn) process.
This is because, on each attempt, the size of the list halves.

Question 8

How do you represent a binary tree?

Answer 8

Binary trees can be represented using three arrays.
One stores the data for each node, one stores the left pointers, and one stores the right pointers.

Pointers are stored at the same location in the arrays as corresponding data item.