Tree-traversal

Question 1

What are the 3 most common algorithms for traversing trees?

Answer 1

Pre-order, post-order and in-order

Question 2

Define pre-order

Answer 2

Specifies the point in traversal where the node contents are processed

Question 3

What happens to a node when it’s visited?

Answer 3

A nodes contents are outputted

Question 4

How many times can a node be visited?

Answer 4

Multiple times but it’s contents can only be processed once

Question 5

What makes pre-order traversal special?

Answer 5

Each node is visited before the algorithm traverses either of the nodes subtrees

Question 6

State the simplified recursive algorithm for a left-right pre-order traversal

Answer 6

Visit the node
Pre-order traverse of nodes left sub tree
pre-order traverse of the nodes right subtree

Question 7

What happens in an in-order traversal?

Answer 7

Each node is visited between each of it’s subtrees

Question 8

State the simplified algorithm for a left-right in-order traversal

Answer 8

Do an in-order traversal of the whole left subtree
visit the node
in-order traverse the right subtree

Question 9

What happens in a post-order traversal?

Answer 9

Each node is visited after both of it’s subtrees

Question 10

State the simplified recursive algorithm for a left-right post-order traversal

Answer 10

Do a post-order traversal of the left subtree
Do a post-order traversal of the right subtree
Visit the node