cst 370: week 5

This week, we learned about binary trees, decrease and conquer, DAGs, topological sorting, Kahn’s Algorithm, and transform and conquer.

Binary trees can be traversed in three main ways: preorder (root–left–right), inorder (left–root–right), and postorder (left–right–root). The height of a binary tree represents the longest path from root to leaf and affects search efficiency.

Decrease and conquer solves problems by reducing their size, by one (topological sort), by half (binary search), or by variable size (BST insertion/search).

Kahn’s Algorithm finds a topological order in a DAG by removing vertices with zero in degree in order.

Transform and conquer changes data before solving such as pre-sorting, which reduces time complexity from O(n²) to Θ(nlogn) by sorting first, then scanning or searching efficiently.