Divide and Conquer

Get comfortable with being uncomfortable. Because when you feel uncomfortable, you're moving forward and exploring new territory. -- Navy Seals

Now we finally can begin our journey in algorithm design.

D&C on Binary Tree

Its structure is kinda like a post order traversal. But the approach is fundamentally different. D&C replies on return values and tabulates the final result from these base cases in a bottom-up fashion. The hard part is usually coming up with a recursive subproblem for the left subtree and right subtree.

In Java, you need to define a customized return type if you want to return more than one value.

Since we go bottom-up, the base case is normally if (root == null).

D&C in an essence, is building up from base cases, and synthesizes the reports from left and right.

D&C on Recursion Tree

Merge sort Quick select Quick sort