Trees

Question 1

Define tree

Answer 1

connected undirected graph with no cycles

Question 2

Define root of a tree

Answer 2

start node for traversals

Question 3

Define branch of a tree

Answer 3

path from root to an end point

Question 4

Define height of a tree

Answer 4

number of edges connected to root node and furthest leaf node

Question 5

Define parent and child mode

Answer 5

• Parent node: node that comes directly before another

- Child node: no children

Question 6

Define binary tree

Answer 6

-rooted tree where every node has at most two child nodes

Question 7

Define binary search tree

Answer 7

ordered to optimise searching

Question 8

Uses for trees

Answer 8

• used in compilers to build syntax trees.
• to represent algebraic and boolean expressions
• speed up searching

Question 9

Records for each nodes will contain:

Answer 9

• the index
• the data
• left child pointer
• right child pointer

Question 10

Which side do you do pre-order tree traversal in?

Answer 10

left side

Question 11

Algorithm of pre-order?

Answer 11

• Output the node
• Left
• Right

Question 12

Which side do you do in-order traversal?

Answer 12

below

Question 13

Algorithm of in-order?

Answer 13

• left
• output the node
• right

Question 14

Which side do you do post-order traversal?

Answer 14

right side

Question 15

Algorithm of post-order?

Answer 15

• left
• right
• output the node

Question 16

Uses of binary search trees

Answer 16

• in order, access the values in ascending order

- reverse in order, access the values in descending order

Question 17

Uses of expression trees

Answer 17

• pre-order, produces the prefix version
• in-order, produces the infix version
• post-order, produces the postfix version