## Lecture 25 - 03/17

### Tree Traversals

• Given a tree, how do we determine order in which to traverse through it?
• DFS (Depth First Search):
• Top-to-bottom, left-to-right traversal, deeper nodes traversed before shallower nodes overall
• Three ways of traversing a tree:
• Preorder traversal (visit node, then traverse its children)
• Like tracing the graph's outline from top going counter clockwise, shout when passing left of node
• Inorder traversal (traverse left child, visit node, then traverse right child)
• Shout when passing bottom of node
• Postorder traversal (traverse left and right children, then visit node)
• Shout when passing right of node
• Example of preorder traversal: getting list of nested file system hierarchy; example of postorder: getting file size for different files in nested hierarchy (to find size of highest level file, need to first know size of all of it's subfile components)
Can implement with something as follows (below is pseudocode, placement of visit statement determines traversal order):
```postOrder(BSTNode x) {
if (x == null) return;
postOrder(x.left);
postOrder(x.right);
x.visit;
}
```
• Can also implement with a stack to store nodes for traversal (LIFO)
• Level-Order Traversal/BFS (Breath First Search):
• We can use iterative deepening to successively traverse each layer of the tree
• If tree is bushy, linear runtime, else if tree is spindly, quadratic runtime
• An improvement involves using a queue fringe to store nodes for traversal (FIFO)
• We will explore this in the coming lectures
• Range Finding:
• Say we want to find all items in a tree between a given min and max
• Simple implementation: traverse entire tree with BFS/DFS, and compare with range
• Better implementation with pruning: if the tree is sorted, we can eliminate/prue subtrees of nodes that lie outside the range
• Spatial Trees:
• We have nodes that have multiple dimensions of data (x, y coordinates), and want to organize the data into a tree so we can quickly prune the tree and find all the data elements that meet a certain search range criteria
• Conflict: in one dimension node A could be greater than node B, but in another dimension it could be the opposite
• Instead, expand the BST idea into a Quadtree
• Current node has a location X, and can have upto four children in the NW, NE, SE, SW quadrants
• Uses two compares (for both x and y coordinates) to decide which direction to go