Introduction to Multi-threaded Pattern

You are asked whether two binary trees are identical. Each tree has a million nodes.

compare root values
compare left subtrees
compare right subtrees

One thread walks both trees and compares as it goes. That is O(N) and it is already optimal in the number of comparisons.

But notice what the two recursive calls do. Comparing the left subtrees never reads or writes anything the right comparison touches. They share no state at all.

Work that shares no state can run at the same time