← Home onlinecstutor.com
Recursion — Tree Traversal

A-LEVEL · TREE TRAVERSAL

Tree traversal <stack meets heap>

Same tree, same recursive walk — switch between pre-order, in-order and post-order to watch how the call stack changes.

Heap — tree structure

Stack — call frames (bottom to top, left to right)

Visited so far — in-order output

Step of

not yet reached on call stack, waiting visited
About this resource · A-Level

Tree traversal and the call stack

There are three depth-first ways to traverse a binary tree. Pre-order visits the node, then the left subtree, then the right. In-order goes left subtree, node, right subtree, which outputs a binary search tree in sorted order. Post-order goes left, right, then node, which is useful for deleting a tree or evaluating expression trees.

All three use the same recursive walk. The only difference is when the node is output. The animation shows each recursive call as a frame on the call stack, so you can see exactly why recursion and stacks are so closely linked.

Switch between the three orders on the same tree and compare the output sequences. Then try drawing your own trees with the tree diagram drawer.

Exam tips

Specification

Tree traversal and recursion, OCR H446 and AQA 7517.

Related resources

Browse all free Computer Science resources →

Want one-to-one help with this topic? I'm Damian Biasone, a qualified Computer Science teacher with 20 years' experience, tutoring GCSE and A-Level students online.

OCR A-Level (H446) tuitionAQA A-Level (7517) tuition