Write a method that finds depth of a (non-balanced) binary tree.

Question

Sigiloso · Accepted Answer

Want an elegant solution? Here it goes.

class Node {
  Node left;
  Node right;
  // other data members relevant to node, e.g. element.
  // constructors, getter/setters, etc.
}

class BinaryTree {
  Node root;
  int height() {
    calcDepth(root);
  }
}

int calcDepth(Node N) {
  if (N == null) return 0;
  return Math.max(calcDepth(N.left)+1,calcDepth(N.right)+1);
}

calcDepth is the method that computes the depth (or height) of a tree.

Sigiloso · Answer

Very nice, but I doubt Google generally takes kindly to recursive solutions.

Sigiloso · Answer

One way is to record each node's depth as it is added in a separate field, implementing it as node.parent.depth() + 1. Then keep track of the max.

Alternatively, do a BFS traversal, incrementing depth of each node every time its parent is selected. Store those depths in a queue; the last element is the overall tree depth. Not pretty, but it should work.

Google

Pergunta de entrevista da empresa Google

Respostas da entrevista

Empresas seguidas

Buscas de vagas