Welcome to CS61B!

Section 107

Agenda

• Announcements
• Tree Traversals
• Cool Trick
• Q1
• BSTs
• Q2

Announcements

• HW5 Due 10/20
• Proj2 due 11/9 (Milestone 11/6)

Tree Traversals

• preorder: process the root, process the left subtree (in preorder), process the right subtree (in preorder)
• postorder: process the left subtree (in postorder), process the right subtree (in postorder), process the root
• inorder: process the left subtree (in inorder), process the root, process the right subtree (in inorder)
• Depth First Traversal (dfs) - push neighboring nodes onto stack, continuously pop from stack (LIFO - Last in First Out)
• Ex: stack of plates at Crossroads
• Breadth First Traversal (bfs) - push neighboring nodes onto queue, continuously remove from queue (FIFO - First in First Out)
• Ex: line for food at Crossroads

​

Cool Trick (link)

• Pass to the left of the node: Preorder
• Pass to the right of the node: Postorder
• Pass beneath the node: Inorder (in a couple of slides)

8

4

7

1

6

5

2

3

Binary Search Trees

• All nodes in left subtree smaller than root
• All nodes in right subtree larger than root
• Left subtree, right subtree also BSTs
• Find, insert, delete operations