Trees

Question 1

What are the two ways you could view a tree as?

Answer 1

Generalisation of a linked list

Specialisation of a graph

Question 2

Define a tree

Answer 2

Abstract data type that simulates a hierarchical tree structure, with a root value and subtrees with children

Question 3

What makes a binary tree special?

Answer 3

Each node has at most two child nodes

Question 4

What three things are stored in a class for a BinaryTreeNode?

Answer 4

element
left node
right node

Question 5

Define traversal

Answer 5

Systematic way of accessing or visiting all the nodes

Question 6

Complexity for insert in a tree

Answer 6

Linear

Question 7

Complexity for contains in a tree

Answer 7

Linear

Question 8

Complexity for remove in a tree

Answer 8

Linear

Question 9

Complexity for size in a tree

Answer 9

Linear

Question 10

What are the four strategies for traversal?

Answer 10

Breadth first
Depth first (in order, post order, pre order)

Question 11

Describe in order traversal

Answer 11

Visit the first child, visit the node, visit the next
node/child
l n r

Question 12

Describe post order traversal

Answer 12

Visit the children, visit the node

l r n

Question 13

Describe pre order traversal

Answer 13

Visit the node, visit the children

n l r

Question 14

Write a recursive function that does pre order traversal of a tree

Answer 14

public void traverse(BinaryTreeNode node){
visit(node.element)
if(node.left !=null) traverse(node.left)
if(node.right !=null) traverse(node.right)
}

Question 15

Write a recursive function that does post order traversal of a tree

Answer 15

public void traverse(BinaryTreeNode node){
if(node.left !=null) traverse(node.left)
if(node.right !=null) traverse(node.right)
visit(node.element)
}

Question 16

Write a recursive function that does in order traversal of a tree

Answer 16

public void traverse(BinaryTreeNode node){
if(node.left !=null) traverse(node.left)
visit(node.element)
if(node.right !=null) traverse(node.right)
}

Question 17

What is an expression tree?

Answer 17

A tree where in each node can hold an operator or an operand
Different traversals generate different notations and results

Question 18

Give the name for this notation and what kind of traversal is used to generate it
+ 2 3

Answer 18

Polish notation

Pre-order traversal

Question 19

Give the name for this notation and what kind of traversal is used to generate it
2 + 3

Answer 19

Infix notation

In order traversal

Question 20

Give the name for this notation and what kind of traversal is used to generate it
2 3 +

Answer 20

Reverse Polish notation

Post order traversal

Question 21

What is another name for breadth first traversal?

Answer 21

Level order traversal

Question 22

What are the two types of search that can be performed on trees?

Answer 22

Depth first search (DFS)

Breadth first search (BFS)

Question 23

Describe a depth first search

Answer 23

Start at the root

Go as far down as possible each branch before backtracking if the goal has not been found

Question 24

Describe a breadth first search

Answer 24

Start at the root
Examine all the child nodes
For each child node, examine it’s child nodes
and so on…

Question 25

Desirable features for searching/sorting data structures in terms of constraints

Answer 25

Unbounded size

Dynamic

Question 26

Desirable features for searching/sorting data structures in terms of operations

Answer 26

Add/remove

Search/sort

Question 27

Desirable features for searching/sorting data structures in terms of complexities

Answer 27

Everything O(1) or as close as possible
Keep operations scale-able