Algorithms and OOD (CSC 207 2013F) : Outlines

# Outline 45: Tree Traversal

Held: Friday, 22 November 2013

Summary

We consider orders in which one might visit the nodes in a tree and the algorithms one uses to achieve those orders.

Related Pages

Overview

Orders for traversing the tree. Implementating traversal algorithms.

• I'll reserve time for questions on the exam.
• Less than half of you have filled out the prologue. Remember that it's due at 5pm today.
• Upcoming extra credit opportunities:
• CS Table today, The New Curriculum
• Hamlet, Today (7:30 pm), Saturday (7:30 pm), Sunday (2:00 pm)
• Swimming, tomorrow (Saturday), 10:00 am.
• Typhoon Halyan Relief benefit show, Sunday, November 24th from 7-9pm in Harris. (If the entry fee is a burden, let me know and I'll give you the money.)
• "Data Sovereignty: The Challenge of Geolocating Data in the Cloud", November 25, 4:15 JRC 101
• "Gold Fever" by Andrew Sherburne '01 or so, 7:00 p.m., Monday, November 25, ARH 302
• Tuesday, November 26, 4:15 p.m., JRC 209 a gaming event with the game [d0x3d!]

## Tree Traversal

• Once we've built a tree, we may want to systematically visit the nodes in the tree. We call that tree traversal.
• There are a number of decisions to make as we design a traversal algorithms.
• If we assume that the children/subtrees are ordered, do we visit them left-to-right or right-to-left? (Yes, there are reasons to do both.)
• Do we delve deeply into a subtree before we go across the tree (depth-first) or do we go across each level of the tree (breadth-first)?
• If we are doing a depth-first traversal, do we visit a node before (preorder), between (inorder), or after (postorder) its children?
• Why after? If we are computing a value based on the children, we need to have the children finished.
• If we are doing a breadth-first traversal, do we go top-down or bottom-up?
• And how do we implement all of these, anyway?
• That's the subject of today's lab.

## Lab

Copyright (c) 2013 Samuel A. Rebelsky.

This work is licensed under a Creative Commons Attribution 3.0 Unported License. To view a copy of this license, visit `http://creativecommons.org/licenses/by/3.0/` or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.