Discussion 9: Tree Traversals, Tries, K-D Trees Christine Zhou Agenda K-D Tree review (with demos from lecture) K-D Tree problems Tree Traversal review Tree Traversal problems Trie review Trie problems Announcements Project 2B is due on Saturday, March 23 at 11:59pm. Remember that these are real deadlines (not "checkpoints") Midterm 2 is on April 5th from 8-10pm. Here are some events to keep on your radar! Check out Hug’s updated kd-tree nearest video @3426 Course Staff Guerrilla Section - 3/31 12-2PM Soda Labs HKN Review Session - 3/31 3-6PM HP Auditorium CSM Review Session - 4/1 6-9PM HP Auditorium Discussion survey: tinyurl.com/cz-disc9-sp19 Tree Traversals Level-Order/Breadth First Search (BFS): ○ Visit top to bottom, left to right, just like how you read! Depth-order/Depth First Search (DFS): ○ Traverse “deeper” nodes before shallow ones Types of DFS: Preorder Pre-Order: “Visit” a node, then traverse its children preOrder(BSTNode x) { if (x == null) return; print(x.key) preOrder(x.left) preOrder(x.right) } Pre-Order: DBACFEG Hack: draw “pegs” on the left side of each node and take a walk around the edges of the tree. The Preorder is the order in which you hit the pegs Types of DFS: Inorder In-Order: Traverse left child, “visit” node, then traverse right child inOrder(BSTNode x) { if (x == null) return; inOrder(x.left) print(x.key) inOrder(x.right)} In-Order: ABCDEFG Hack: draw “pegs” on the bottom of each node and take a walk around the edges of the tree. The Inorder is the order in which you hit the pegs Types of DFS: Postorder Post-Order: Traverse children, then “visit” node. postOrder(BSTNode x) { if (x == null) return; postOrder(x.left) postOrder(x.right) print(x.key) } Post-Order: ACBEGFD Hack: draw “pegs” on the right side of each node and take a walk around the edges of the tree. The postorder is the order in which you hit the pegs Problem 1.1