CMPT 225 Lecture Notes - Lecture 4: Big O Notation, Binary Tree, Linked List

• School: Simon Fraser University
• Department: Computing Science
• Course: CMPT 225
• Professor: David Mitchell

Document Summary

Return 1 + height (u) return 1 + max{height(left(v)), height(right(v))} return 0 if v has one child else. Standard traversals are: traversal of a graph is a process that visits each of its nodes once level order: pre-order, post-order in-order. Visit all nodes at that level before any nodes at level i + 1. Visit nodes at level i left to right . Pre-, in-, and post- order traversals begin at root, recursively visit all nodes in left and right sub trees. Differ in relative order of visiting root and two subtrees. * visit = do work needed to be done pre-order-t(v) here all nodes in left sub tree are visited before any nodes in the right sub tree visit v pre-order-t(left(v)) pre-order-t(right(v)) In-order - visit v in between visits to its children. Post-order visit v after its children post-order-t(left(v)) post-order-t(right(v)) visit v in-order-t(left(v)) visit v in-order-t(right(v)) post-ordr-t(v) in-order-t(v)