Topic study hub
Tree-traversal
Official AQA 7517 section 4.3.2.
0
Objectives
5
Flashcards
7
Questions
36 min
Study time
AqaA LevelComputer ScienceFundamentals of algorithms
Choose a revision tool
Start revising Tree-traversal
Syllabus checklist
What you need to know
0 objective pages available
Simple tree-traversal algorithms1 objectives
- Simple tree-traversal algorithms: Be able to trace the tree-traversal algorithms: • pre-order • post-order • in-order. Be able to describe uses of tree-traversal algorithms. Pre-Order: copying a tree. In-Order: binary search tree, outputting the contents of a binary search tree in ascending order. Post-Order: Infix to RPN (Reverse Polish Notation) conversions, producing a postfix expression from an expression tree, emptying a tree.
Key terms
Tree traversalReverse Polish Notation (RPN)
Exam tips
- Write the traversal rule before tracing: Before following the tree, write the relevant order: pre-order current-left-right, in-order left-current-right, or post-order left-right-current.
Common mistakes
- Putting the root in the wrong position: Remember the three patterns: pre-order is current-left-right, in-order is left-current-right, and post-order is left-right-current.
Practice preview
- Consider this tree: M is the root; M has left child F and right child T; F has left child C and right child H; T has left child R and right child W. What is the pre-order traversal?
- The values in the following binary search tree are arranged so that an in-order traversal should produce them in ascending order. Which sequence is produced by an in-order traversal of this tree: root 50, left child 30, right child 70, 30's children 20 and 40, and 70's children 60 and 80?
- An expression tree has * as its root. Its left subtree has + as its root with leaves a and b, and its right subtree is the leaf c. What postfix expression is produced by a post-order traversal?
Continue by objective
Objectives are grouped by subtopic so students can jump straight to the exact skill they want to revise.
Related topics