A-LEVEL · TREE TRAVERSAL
Same tree, same recursive walk — switch between pre-order, in-order and post-order to watch how the call stack changes.
Step of
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.
Tree traversal and recursion, OCR H446 and AQA 7517.
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