Trees

Question 1

What is a Node?

Answer 1

• The elements of the tree
• Each node contains a key which uniquely identifies that node

Question 2

What is an Edge?

Answer 2

The link/connection between nodes

Question 3

What is unique about the root node?

Answer 3

It has no parent

Question 4

What are leaf nodes?

Answer 4

Nodes that have no child

Question 5

What is a Path?

Answer 5

A sequence of nodes connected by edges

Question 6

How is the length of a path determined?

Answer 6

Determined by the number of nodes in the path (including start and end nodes)

Question 7

What is a Parent node?

Answer 7

The unique predecessor of every node

Question 8

What is a Child node?

Answer 8

The successor to a parent node

Question 9

What are Sibling nodes?

Answer 9

Nodes that have a common parent

Question 10

What is the Level of a node?

Answer 10

• The number of nodes between this node and the root node
• Calculated using the shortest path to the root node

Question 11

What is the height of a tree?

Answer 11

The height is determined by the highest level node

Question 12

What are Sub-trees?

Answer 12

• A Sub-tree is formed using a parent node and all of it’s descendants.
• The parent node becomes the root node of the Sub-tree.

Question 13

What is the difference between a Strictly Binary Tree and a Knuth Binary tree?

Answer 13

• Each node in a Strictly Binary tree has either 0 or 2 sub-trees
• Each node in a Knuth Binary Tree can have 0, 1 or 2 sub trees

Question 14

What 3 qualities make Trees a recursive data structure?

Answer 14

1. The data of the node itself
2. A reference to the left child node (can be null)
3. A reference to the right child node (can be null)

Question 15

What makes a tree balanced?

Answer 15

All leaf nodes have the same level

Question 16

What is a Breadth-first traversal?

Answer 16

Returns the data of each node level by level

(e.g. returns all nodes at level 1, then level 2, etc.)

Question 17

What is the procedure for a Depth first Pre-order traversal?

Answer 17

1. Process current node
2. Traverse to left sub-tree
3. Return to parent node
4. Traverse to right sub-tree
5. Return to parent node

-Process, Left, Right or P, L, R

Question 18

What is the procedure for a Depth first In-order traversal?

Answer 18

1. Visit current node
2. Traverse to left sub-tree
3. Process current node
4. Traverse to right sub-tree
5. Return to parent node

• Left, Process, Right or LPR

Question 19

What is the procedure for a Depth first Post-order traversal?

Answer 19

1. Visit current node
2. Traverse to left sub-tree
3. Visit current node
4. Traverse to right sub-tree
5. Process current node
6. Return to parent node

• Left, Right, Process or LRP

Question 20

What is a Binary Search Tree (BST)?

Answer 20

• A Binary Tree that is ordered so that, starting at the root, when we search for a node we always know which sub tree to search in
• This mean the maximum number of comparisons = height of tree

Question 21

How is a BST organised?

Answer 21

• The values in the left sub-tree are always less than the parent

-The values in the right sub-tree are always greater than the parent

Question 22

What is the worst-case and best-case time complexity of searching a BST?

Answer 22

• Worst case: O (n) when every parent node only has one child
• Best case: O (log n) when every parent node has 2 children

Question 23

What type of traversal is needed to return an ordered list of items from a BST?

Answer 23

Depth first in-order traversal

Question 24

What is a Full Binary tree?

Answer 24

A binary tree where every level of the tree has the maximum possible number of nodes

Question 25

What is a **B-Tree**? (not a binary tree)

Answer 25

A tree where nodes contain multiple key values, and have multiple children

Question 26

What are the benefits of a B-Tree?

Answer 26

- Can be efficiently stored in files and memory - Minimise disk reads ( complexity of O (log n)

Question 27

What are the applications of a B-Tree?

Answer 27

- Suitable for datasets that are too large to fit in main memory - Useful for databases and file systems

Question 28

What are the limitations of a B-Tree?

Answer 28

- Often half empty (inefficient use of space) - Sequential access requires revisiting nodes

Question 29

What is the degree/order of a B-Tree?

Answer 29

The order (M) of a B-Tree is the maximum number of children allowed per parent

Question 30

How many children does each node of a B-Tree have?

Answer 30

**Between M and M/2** with M being the order of a B-Tree

Question 31

How many key values do parents have in a B-Tree?

Answer 31

- Number of children -1 - So for a parent with 4 children, it would have 3 key values

Question 32

Describe the Node splitting method

Answer 32

1. When a node is full (M elements), split into two nodes at the same level as the original node 2. Put the smallest elements into the left node 3. Put the largest elements into the right node 4. Insert the middle element into the parent node 5. If no parent node exists, create a new root node and insert the middle element

Question 33

How do you convert this **infix** expression: **(A + B) * C - D / E** into a **prefix** expression?

Answer 33

1. (A + B) = **AB+** 2. (A + B) * C = **AB+C*** 3. D / E = **DE/** **AB+C*DE/-**

Question 34

Why are expressions converted into **prefix** forms?

Answer 34

- Can be processed with a single left to right pass - Easier to build an expression tree

Question 35

How are expression trees formatted?

Answer 35

- **Parent node** will be the operator - **Child nodes** will be the two elements being processed e.g. the parent node could be **+** and the child nodes would be the element **A**, and the subtree **B*C** (will be processed recursively)

Question 36

How is a modified **in-order** traversal used to evaluate an expression tree?

Answer 36

1. IF parent node, then print ( 2. Left 3. Process 4. Right 5. IF parent node, print )

Question 37

How is a **post order** traversal used to evaluate an expression tree?

Answer 37

- Left, Right, Process - Using a stack data structure means we don't need parentheses e.g. ABCD-*+ will return: C-D, B*(C-D), A+B*(C-D)