# 08 - Trees

1. In computer science, a tree is a widely used data structure that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of _______________.

text-based nodes

isolated nodes

numbered (and with a maximum of 8) nodes

2. Which of the following are valid applications of trees in the field of computer science?
```1. Binary Space Partition
===========================
Used in almost every 3D video game to determine
what objects need to be rendered.

===========================
Used in almost every high-bandwidth router
for storing router-tables.

3. Huffman Coding Tree
============================
Used in compression algorithms,
such as those used by the .jpeg and .mp3
file-formats.``` 1 only

All the options are valid and are examples of the use of trees in computing

1 and 2 only

2 only

3. Read the following excerpt that highlights the difference between Queues and Stacks and Trees. Fill in the blanks
```The QUEUE and the STACK can essentially be thought of as linear lists.
This means each data item only points to the one before it and after it.

Queues and Stacks have the concept or sense of order that is built into them,
such as 'last' or 'first', but the reality is that there is no implication of
any relationship between the data items themselves.

The TREE however, is designed to represent ___________________________________```

the highest implementation (in the sense of being superior) of a stack

the fastest implementation of a hybrid stack-queue data structure

the relationship between data items

the relationship between a stack and a queue

4. The image below shows a simple unordered tree. Which of the following statements are accurate?
```1. The node labeled 7 has two children, labeled 2 and 6,

2. The node labeled 7 has one parent, labeled 2.

3. The root node is 4 and has no parent

4. The node labeled 2 is known as the 'first child' node. ``` Statements 1 and 4 are correct

Statements 3 and 4 are correct

Only statement 1 is correct

Only statements 1 and 2 are correct

5. The tree with no nodes is called a null or empty tree

TRUE

FALSE

6. A node with no children is called a:

parent

leaf

internal or branch node

edge

7. A node with at least one child is called an:

parent

edge

leaf

internal or branch node

8. The connection between one node and another node is called an:

internal or branch node

parent

leaf

edge

9. A group of nodes with the same children are called 'siblings'

FALSE

TRUE

10. The ______of a node is defined as: 1 + the number of edges between the node and the root

depth of a node

height of a tree

level

height of a node

11. The ___________is the number of edges on the longest path between that node and a leaf.

height of a node

level

height of a tree

depth of a node

12. The ________ is the height of its root node.

depth of a node

height of a tree

height of a node

level

13. The _______ is the number of edges from the tree's root node to the node.

height of a node

height of a tree

level

depth of a node

14. As a data type, a tree has a value and children, and the children are themselves _____

level-free

depth-first

set to a height of zero

trees

15. A __________ is a type of tree in which a parent node has only two child nodes.

sorted T-type tree

binary tree

height-first tree

depth-first tree

16. ____________ traversal would give: 4251637 post-order

in-order

pre-order

17. ____________traversal would give: 1245367 post-order

in-order

pre-order

18. ___________traversal would give: 7635421 pre-order

in-order

post-order

19. __________ would give: 1234567 pre-order

post-order

in-order

20. Which of the following statements are correct in either describing the advantages of the use of trees or defining the function of a tree.
```1. Trees reflect structural relationships in data which are useful

2. Trees are used to represent heirarchies

3. Trees provide an efficient insertion and searching method

4. Trees are very flexible data structures, allowing the move of
sub-trees around with minimum effort. ```

Statement 3 only

Statement 2 and 3

Statement 1,2,3 and 4

Statement 1 and 2