4.3.2 Tree Traversal Flashcards
What is tree traversal?
The process of visiting/updating/outputting each node in a tree.
It is an Algorithm
What is an algorithm?
A set of instructions with a set of instructions that complete in a finite amount of time and always terminates upon the completion of a task.
Name the three types of tree-traversal.
Preorder, inorder, post-order
Name a use of postorder traversal.
- Emptying a tree
- Infix to RPN
- Producing a postfix expression from an expression tree
Which tree-traversal would be used for copying the tree?
Preorder traversal
Name a use of inorder traversal?
Outputting the contents of a binary search tree in ascending order.
Can inorder traversal be performed on any tree?
No, only binary trees
Can preorder traversal be performed on any tree?
Yes
Can postorder be performed on any tree?
Yes
Where does tree traversal start?
At the root node
How do traversals work their way around a tree?
Anticlockwise
Where does the dot go for inorder?
Bottom
Where does dot go for preorder
Left
Where does dot go for postorder
Right
