Blackcap Blog

Published at 09:56 on 30 July 2021

Trees Are Stupid

Not the living beings (those are amazing), the data structures. The things my undergrad CS teachers were obsessed with assigning tedious programming exercises to implement.

I am reviewing how to pass those stupid coding tests most interviewers seem to be so fond of these days, and one if the things that has become clear is just why I never much liked trees in the first place. In short, if you use trees, you are virtually always stuck with two choices: a simple, logical, easy-to-understand tree that is vulnerable to pathological behavior, or a complex, quirky, difficult-to-understand one that literally makes buggy code inevitable.

Yet my professors pissed away so much time blathering about trees and how to code them. How many times have I used, I mean actually used, such knowledge professionally? Maybe once or twice in my decades-long career. Not surprising, given their many disadvantages.

Consider associative arrays (a.k.a. dictionaries or hash maps), which all modern programming languages support to some degree. These are versatile general-purpose data structures that eliminate much low-level grunt work. A huge part of the reason I so seldom use trees is that I just use associative arrays instead.

Ah, but don’t these use trees under the hood? No, generally they do not. They use hashing functions, arrays, and linked lists. Why? Because you typically get faster access that way, and they are simpler to code (and therefore have fewer chances of implementation bugs), that’s why. The people who code language runtimes and standard libraries are not stupid.

Yes, even in what is alleged to be the canonical “trees excel at this” case, they actually don’t. Not really.

Sure, trees have some genuine uses in databases. But here’s the thing about databases: very few people write them. This is because few people need to write them. The rest of us simply use them, and there is already a very nice set of databases (well debugged) out there ready to be used. Why re-invent the wheel, particularly when it would involve so much tedious, bug-prone coding?

So it’s not that trees are useless, it’s just that they are far less useful than their prominence in the undergraduate computer science curriculum would indicate.

Why are they so common, then? One must consider the general purpose of higher education: to furnish to the economic system individuals that are screened and graded for both intelligence and obedience to authority. Seeing who is motivated to perform meaningless, tedious programming exercises is a great way to do this. As a bonus, many of the more sophisticated tree structures have the advantage of requiring algorithms that are both non-trivial enough to give students a good coding exercise yet trivial enough for them to be expected to code in the first place, thus making them a good source of busywork.

Job Interview Coding Tests Are Stupid

They are stupid precisely because they inevitably want you to show off your tree-coding knowledge. But as we have seen, in the real world, you don’t directly touch trees. You use a database or a hash map, and be done with it. This goes for a surprising amount of the generalized stuff they teach you in college, in fact.

Seeing the world in terms of general-purpose principles can often be positively harmful in programming. Some of the most useful code I have written for people is code that was proclaimed by others to be impossible to write, because it was an instance of a generally impossible problem to efficiently solve. While this was true in the general case, a little introspection into the particular instance of the problem at hand would reveal it had specific attributes that made a solution possible. The general case would break my code, but that was irrelevant because my code was not running against the general case. A solution was possible.

In one case, there was so much resistance from others in the team that I had to sneak my code into the system. It was only some weeks later that I observed how things were “mysteriously” behaving better, and then pointed out the reason to my incredulous teammates, who were at that point compelled to concede that the problem was solvable after all.

Success in real-world coding is based on being able to determine the unique and specific characteristics of a particular problem, how these differ from the more general cases of problems, and how to leverage these particulars to craft specific solutions that are significantly more efficient than any stock algorithms or data structures could ever be.

I will make an exception here for the coding test that my passing led me to get hired at the best job I have ever worked at (at least for the initial several years, until both the job and the company changed to the point that I was no longer well-suited to the position). It was crafted to have such realistic special characteristics, and it was my quick spotting of these that impressed my interviewers.

But that was the exception that proved the general rule: interview coding tests are stupid.