ECE250 Lecture Notes - Lecture 12: Tree Traversal, Abcdefg (Album), Glossary Of Arithmetic And Diophantine Geometry

• School: University of Waterloo
• Department: Electrical and Computer Engineering
• Course: ECE250
• Professor: Douglas Harder

Document Summary

Tree traversals: breadth-first traversals: visit all nodes at depth k before preceding to the nodes at depth k + 1. Push all the elements onto the queue based on depth. Memory can be expensive: maximum nodes can potentially be at the lowest nodes. Order in queue: a b h c d g i e f j k: depth-first traversals: visit all the deepest nodes possible before visiting the other nodes. At any node, we proceed to visit the first child who have not been visited yet. If we visited all the child nodes, we backtrack to the parent and repeat the decision making process again. End once all the children of the root node have been visited. Note that the node can be visited twice: First time when the node was approached (to determine if the node has child nodes) The last time the node was approached (after when all the children have been visited)