Traversing linked lists and trees

Overview

Traversal of a linked list, three traversals of a binary tree and in-order traversal.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is a traversal?

   Model answer

   A traversal visits every node of a data structure exactly once. The order of the visits depends on the algorithm chosen.

2. 2

   Describe the traversal of a linked list.

   Model answer

   A current pointer is set to the start pointer and the data at that node is output. The current pointer then moves to the next node until null is reached.

3. 3

   Write pseudo-code for the traversal of a linked list.

   Model answer

   The code is current = start, then WHILE current <> null, then OUTPUT data[current] and current = next[current], then END WHILE. The loop ends at the null pointer of the last node.

4. 4

   Name the three traversals of a binary tree.

   Model answer

   The three traversals of a binary tree are pre-order, in-order and post-order. Each differs in when the root of a subtree is visited.

5. 5

   Describe an in-order traversal.

   Model answer

   An in-order traversal visits the left subtree, then the node itself, then the right subtree. The same rule is applied at every node.

6. 6

   Describe a pre-order traversal.

   Model answer

   A pre-order traversal visits the node itself, then the left subtree, then the right subtree. The root of each subtree comes first.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.