A-level Computer Science revision · Data structures and algorithms

Tree traversal

The idea

Tree traversals visit every node. Pre-order: root, left, right. In-order: left, root, right (gives sorted order for a BST). Post-order: left, right, root. Depth-first search goes deep before backtracking (using a stack); breadth-first visits level by level (using a queue).

  1. Pre-order: visit node before its subtrees.
  2. In-order on a BST: ascending order.
  3. Breadth-first: queue; depth-first: stack.

Watch out In-order traversal only gives sorted output for a binary search tree.

See it worked

Worked example

A BST has root 8, left 3, right 10. What is the in-order traversal?

  1. Left subtree first: 3.
  2. Then root: 8.
  3. Then right: 10.

Answer 3, 8, 10

Your turn

Question 11 mark

Which traversal visits the root first?

Choose one
Question 21 mark

Which data structure does breadth-first search use?

Choose one
Question 31 mark

Root A has left child B and right child C; B has left child D. What is the post-order traversal?

Choose one

A-level Computer Science Pro, OCR H446

A-level Computer Science Pro

£119 once

Price rises to £199 on 1 January. Save £80 by joining before then.

At least 12 months of access

By paying you agree to our Terms and get access straight away, which ends your 14-day cancellation right.

No VAT is charged.

Independent practice for OCR A-level Computer Science (H446), not endorsed by OCR.

Privacy · Terms