Traversing a tree: depth-first and breadth-first

Overview

Recall questions on depth-first and breadth-first traversals, pre-order, in-order and post-order rules and their uses, tracing each on a binary search tree, reverse Polish from an expression tree, memory use, and time complexity.

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 does traversing a tree mean, and why is more than one traversal needed?

   Model answer

   Traversing means visiting every node exactly once in a defined order and doing something with each, such as outputting its value. Different orders are needed because the order determines what the output means: one order produces the values in sorted sequence, another produces a form suitable for evaluation, another copies the structure faithfully.

2. 2

   Describe a depth-first traversal in general terms and say which structure supports it.

   Model answer

   A depth-first traversal follows one branch as far down as it will go before backtracking to take the next branch. It needs a stack to remember the nodes it must come back to; if it is written recursively the call stack does that job automatically.

3. 3

   State the three depth-first orders, and say which one is meant if someone asks simply for a depth-first traversal of a tree.

   Model answer

   Pre-order visits the node, then the left subtree, then the right subtree. In-order visits the left subtree, then the node, then the right subtree. Post-order visits the left subtree, then the right subtree, then the node. Post-order is the one taken to be meant by depth-first traversal of a tree, so if a question asks for a depth-first traversal without saying which order, give the post-order output.

4. 4

   Give the rule for a post-order traversal in a form you can apply at every node.

   Model answer

   At any node: traverse its left subtree in post-order, then traverse its right subtree in post-order, then output the node itself. The node is always dealt with last, so a parent can never be output before either of its children.

5. 5

   A binary search tree has root 50, whose left child is 30 with children 20 and 40, and whose right child is 70 with children 60 and 80. Give the post-order traversal.

   Model answer

   20, 40, 30, 60, 80, 70, 50. Within the left subtree, 20 and 40 are output before their parent 30; within the right subtree, 60 and 80 are output before their parent 70; and the root 50 comes last of all.

6. 6

   A binary search tree has root 50, whose left child is 30 with children 20 and 40, and whose right child is 70 with children 60 and 80. Give its in-order traversal, and say what is special about the result.

   Model answer

   20, 30, 40, 50, 60, 70, 80. The values come out in ascending order. This happens for any binary search tree, because the ordering rule guarantees everything in the left subtree is smaller than the node and everything in the right subtree is larger, so visiting left, node, right produces a sorted sequence.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.