Trees and Traversals Preparation

Overview

We will finally move away from linear structures and start thinking about ways of storing data that have more complicated connections. Today we’ll focus on a group of structures referred to as trees due to their ability to branch. An interesting thing about trees is that the order in which you go through the nodes, traversing, can greatly change based on what you are trying to accomplish!

Basic Learning Objectives

Before class, you should be able to:

• Explain what the tree ADT is
• Explain how a tree data structure can be implemented
• Explain what the three tree traversals are

Advanced Learning Objectives

After class, you should be able to:

• Implement your own code for traversing a tree in three different orders

Resources

You should read the following:

• 6.2 Examples of Trees
• 6.3 Vocabulary
• 6.6 Nodes and References
• 6.8 Tree Traversals

Checks

Submit answers to the following on Moodle.

Given this tree:

1. What is the result of an inorder traversal?
2. What is the result of a preorder traversal?
3. What is the result of a postorder traversal?

Acknowledgements

Check question from Prof. Jean Salac.