Why not just publicly collect the companies that are known to not ask applicants to "invert a binary tree"? This would generate an incentive for companies.

The data could be community-driven, but of course that risks sufficiently big players fudging the input data (sort of like the fake reviews on e.g. Amazon). Even so, it may be possible to detect which companies are faking it.