Tree Traversals

Question 1

What is graph traversal?

Answer 1

The process of systematically visiting each node in a graph.

Question 2

What is breadth first traversal?

Answer 2

Nodes closest to the start node are visited first.
E.g. finding the shortest path through an unweighted graph (Dijkstra).

Question 3

What is depth first traversal?

Answer 3

Exploring as far as possible away from the start node.
E.g. solving puzzles like mazes.

Question 4

What is the time complexity of tree traversals?

Answer 4

O(n) because every node is visited once.

Question 5

What are the three types of tree traversal?

Answer 5

Pre-order, in-order and post-order.
All tree traversals are depth first traversals.

Question 6

Explain pre-order traversal.

Answer 6

Pattern: visit, left, right
Use: copying a tree

In pre-order traversals, the node is visited before traversing its left and right subtrees.
That’s why the root is the first node outputted.

Question 7

Explain in-order traversal.

Answer 7

They are used for binary search trees only.

Pattern: left, visit, right
Use: outputting a binary search tree in ascending order

In-order traversals will output the contents of a binary search tree in order. It only outputs the node once all the nodes on its left have been output.

Question 8

Explain post-order traversal.

Answer 8

Pattern: left, right, visit
Use: converting infix to RPN (RPN is post-fix)

Post-order only outputs the node once it has output all the nodes on its left and right. The root is the last node to be output/visited.