Calculating binary tree height as asked in the interview

Question

Input:

The first line contains the number of vertices \$n\$. The second line contains \$n\$ integer numbers from the range \$\left[−1, n − 1\right]\$ representing the \$0\$-based index of the parent for each vertex. An index of \$-1\$ designates that vertex as a root without a parent.

It is guaranteed that there is exactly one root.
It is guaranteed that the input represents a tree.

Output:

Output the height of the tree.

Code:

console.clear();

function heightSlow(parent) {
  var maxHeight = 0;
  // for each vertex check its height
  // and keep track of maximum height so far.
  for (var i = 0; i < parent.length; i++) {
    var height = 0;
    // O(n*n) // n is the number of vertex
    for (var vertex = i; vertex != -1; vertex = parent[vertex]) {
      height++;
    }
    // vertex should be -1 here
    maxHeight = Math.max(maxHeight, height);
  }
  return maxHeight;
}

function heightFast(parent) {
  var depth = [];
  var N = parent.length;

  function recur(parent, i, depth) {
    if (depth[i] !== 0) return;

    if (parent[i] === -1) {
      depth[i] = 1;
      return;
    }

    // Find the depth of parent
    if (depth[parent[i]] === 0) recur(parent, parent[i], depth);

    // We have depth of the parent now
    depth[i] = depth[parent[i]] + 1;
  }

  var vertex;
  // fill with default depth, although I could use null
  // but stick with general notion of invalid value mathematically
  // Theta(N)
  for (vertex = 0; vertex < N; vertex++)
    depth[vertex] = 0;

  // find depth of each node
  // recursion would be called for each node but
  // it would return immidiately hence we can ignore that call?
  // if yes then recur would be called N times exactly. Hence,
  // Theta(N)
  for (vertex = 0; vertex < N; vertex++)
    recur(parent, vertex, depth);

  // get the max depth, which is height
  // Theta(N)
  var height = 0;
  for (vertex = 0; vertex < N; vertex++) {
    height = Math.max(height, depth[vertex]);
  }
  return height;
}

// O(N^2)
console.log(heightSlow([4, -1, 4, 1, 1])); // 3
console.log(heightSlow([-1, 0, 4, 0, 3])); // 4

// Theta(N)
console.log(heightFast([4, -1, 4, 1, 1])); // 3

console.log(heightFast([-1, 0, 4, 0, 3])); // 4

Disclaimer:

I am more interested in fail proof approaches like writing correct loops, making quick tests without any testing frameworks to check the code correctness and finally reasoning about the run time complexity.

Having said that I would like to adhere to the problem specification in past I saw people arguing about the best practices which doesn't match with the problem statement and hence becomes immaterial.

Answer 1

There is no input/output handling in your code.

Even though it is fine to implement the algorithm in isolation, and also to base your unit tests on the backing implementation, handling input and output was part of the problem specification.

If this was for an interview, you would have missed to fulfill the specification.

---

Having said that I would like to adhere to the problem specification in past I saw people arguing about the best practices which doesn't match with the problem statement and hence becomes immaterial.

Even if the problem specification gives you guarantees about the input being well formatted, you still should take care to handle invalid inputs gracefully.

Both of your implementations e.g. get caught in an infinite loop, should the input contain a directed graph with loops instead of a tree. Your second implementation will even exhaust the call stack eventually.

Simply limiting the recursion depth / iteration count to the number of input elements would have protected you against that.

Verifying that there is only a single root node, or that all indexes are valid would have easily fit within the budget as well. Even though your algorithms would just throw an exception / yield nonsensical results in that case, so it's not as critical as the loop case.

As it stands, your code is a potential vector for a DoS attack and should therefor not be used in any publicly accessible environment.

---

function recur(parent, i, depth) {
  if (depth[i] !== 0) return;

  if (parent[i] === -1) {
    depth[i] = 1;
    return;
  }

  // Find the depth of parent
  if (depth[parent[i]] === 0) recur(parent, parent[i], depth);

  // We have depth of the parent now
  depth[i] = depth[parent[i]] + 1;
}

Recursions are nasty in JavaScript, because the maximum recursion depth is pretty low on some platforms: https://stackoverflow.com/a/7828803/2879325

You should try to express this in iterative form if possible, especially since the problem specification does not provide you with an upper bound!

---

// O(N^2)
console.log(heightSlow([4, -1, 4, 1, 1])); // 3
console.log(heightSlow([-1, 0, 4, 0, 3])); // 4

// Theta(N)
console.log(heightFast([4, -1, 4, 1, 1])); // 3
console.log(heightFast([-1, 0, 4, 0, 3])); // 4

That's an usage example, but it's not a unit test. If you don't want to use a fully fleshed testing framework, the least you can do is something this:

function test(functor, expected) {
  var result;
  try {
    result = functor();
  } catch(e) {
    console.error(Function.prototype.toString.call(functor), e, expected);
  }
  // Object comparison hack
  if (JSON.stringify(result) !== JSON.stringify(expected)) {
    console.error(Function.prototype.toString.call(functor), result, expected);
  }
}

// O(N^2)
test(function (){return heightSlow([4, -1, 4, 1, 1])}, 3);
test(function (){return heightSlow([-1, 0, 4, 0, 3])}, 4);

// Theta(N)
test(function (){return heightFast([4, -1, 4, 1, 1])}, 3);
test(function (){return heightFast([-1, 0, 4, 0, 3])}, 4);

That provides you with simple unit tests which are both machine checked and easy to comprehend in case of an error.

Just beware that this is not exactly robust with regard to run time errors, such as exhausting the recursion limit!

---

As for your choice of test cases, you didn't test anything but trivial cases.

The most bugs however usually hide in edge cases, such as:

• Minimal input
• Degenerated input (sequential list or all nodes are children of root)
• Malformed input (duplicate root, no root, loops)
• Large inputs (long sequential list, exhausting the recursion limit!)

---

// find depth of each node
// recursion would be called for each node but
// it would return immidiately hence we can ignore that call?
// if yes then recur would be called N times exactly. Hence,
// Theta(N)

The conclusion is correct, but the argumentation is incoherent.

Your argument is that you are calculating the height of each node exactly once, plus a total of \$n\$ comparisons to verify that each node has either been computed yet, which amounts to a total of \$2n\$ calls to recur().