Tree traversal

Overview

Recall questions on pre-order, in-order and post-order traversal, what each is used for, and producing all three orders for a given binary tree.

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

   Name the three tree-traversal algorithms and state the order in which each deals with a node and its subtrees.

   Model answer

   Pre-order visits the node first, then traverses the left subtree, then the right subtree. In-order traverses the left subtree first, then visits the node, then traverses the right subtree. Post-order traverses the left subtree, then the right subtree, and visits the node last. In all three the left subtree is dealt with before the right; only the position of the node itself changes.

2. 2

   Describe the pre-order traversal algorithm.

   Model answer

   Starting at the root: output the value at the current node, then apply the same procedure recursively to its left subtree, then apply it recursively to its right subtree. If a subtree is empty, nothing is done for it and the algorithm returns.

3. 3

   Describe the in-order traversal algorithm.

   Model answer

   Starting at the root: apply the procedure recursively to the left subtree, then output the value at the current node, then apply the procedure recursively to the right subtree. If a subtree is empty, nothing is done for it and the algorithm returns.

4. 4

   Describe the post-order traversal algorithm.

   Model answer

   Starting at the root: apply the procedure recursively to the left subtree, then apply it recursively to the right subtree, and only then output the value at the current node. If a subtree is empty, nothing is done for it and the algorithm returns.

5. 5

   A binary tree has root A with left child B and right child C. B has children D and E. C has a right child F and no left child. Give the pre-order traversal.

   Model answer

   A, B, D, E, C, F. A is output first, then the left subtree rooted at B gives B, D, E, then the right subtree rooted at C gives C, F.

6. 6

   For the same tree — root A, children B and C; B has children D and E; C has right child F — give the in-order traversal.

   Model answer

   D, B, E, A, C, F. The left subtree rooted at B gives D, B, E; then A itself; then the right subtree rooted at C gives C, F, because C has no left child so C is output before F.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.