Would the interviewer be right?

Please avoid stating which problem these are solutions for.

During a recent discussion the following code was suggested

int desc(const Node* node, int d)
{
  int l = d, r = d;
  if (node->l) l = desc(node->l, d + 1);
  if (node->r) r = desc(node->r, d + 1);  // edit: thanks, Nico
  return max(l, r);
}
int d2(const Node* root)
{
  return root ? desc(root, 1) : 0;
}

One of the folks in the discussion shook his head and said: “If this was an interviewer, they would want you to do it in one function, though”. Then he presented this:

int d1(const Node* root)
{
  if (root == nullptr) return 0;
  return max(d1(root->l) + 1, d1(root->r) + 1);
}

Then he made the assertion “this is what an interviewer would be looking for”.

I suspect that what he meant was “I’ve asked this question in interviews and this is the answer I look for”.

The second version of the code has a number of merits: its shorter, there’s just one function… If you moved the +1 outside the max, it has a little less duplication.

But it’s not the same code. It seems to me that, in the context of an interview, you’d probably want to start with clearer code for walking through your process and consider reducing your code during the process.

On a whim, I decided to look at both versions under the microscope. It turns out that the snazzy 3-liner version gets significantly slower as the trees get larger.

    return 1 + max(d1(root->l), d1(root->r));

The compiler is forced to call d1 on root->l and root->r for every node it visits compared to the original version

  if (node->l) l = desc(node->l, d + 1);
  if (node->r) r = desc(node->r, d + 1);

This version of the code has an extra conditional overhead in the trampoline function that checks if the tree is empty, but once we get into desc the test is used to make calls conditional, rather than having to make the call to test the condition.

And the performance difference is quite impressive: For a roughly-balanced 1,000 node tree, Visual Studio sees a near 50% improvement in the first version (first version = d2), Clang with -O3 shows 37% improvement and GCC is almost 50% again.

Finally, if we look at the assembly this generates, the short version generates 740 lines while the original version generates 1700.

So, all things considered, would the interviewer have been right?