Find height of a tree without using recursion

Question

I want you to pick my code apart and give me some feedback on how I could make it better or simpler.

public int heightHelper(TreeNode node) {
 int height = -1;
 if (node == null) return height;
 final Queue<TreeNode> queue = new LinkedList<TreeNode>();
 queue.add(node);
 int currentLevelNodeCount = 1;
 int nextLevelNodeCount = 0;
 while (!queue.isEmpty()) {
 TreeNode current = queue.poll();
 currentLevelNodeCount--;
 if (current.left != null) { queue.add(current.left); nextLevelNodeCount++; }
 if (current.right != null) { queue.add(current.right); nextLevelNodeCount++; }
 // current level is done.
 if (currentLevelNodeCount == 0) {
 height++;
 currentLevelNodeCount = nextLevelNodeCount;
 nextLevelNodeCount = 0;
 }
 }
 return height;
}

Answer 1

The code is basically sound.

It's not a helper function, so don't name it as such. (Helper functions would usually be private.)

Comments would be good. In particular, a JavaDoc explaining how to interpret the height of a degenerate tree would be helpful.

Your currentLevelNodeCount and nextLevelNodeCount are basically segmenting the queue into two queues the hard way. Why not reduce the bookkeeping by using two queues? (I've named them thisLevel and nextLevel because variable names that have the same length make the code look pretty.)

A few tweaks here and there make the code slightly more compact.

/**
 * Returns the maximum depth of a tree.
 *
 * @param node The root of the tree
 *
 * @return -1 if node is null, 0 if node has no children,
 * a positive number otherwise.
 */
public int height(TreeNode node) {
 int height = -1;
 if (node != null) {
 // Breadth-first traversal, keeping track of the number of levels
 Queue<TreeNode> thisLevel = new LinkedList<TreeNode>(),
 nextLevel = new LinkedList<TreeNode>();
 thisLevel.add(node);
 while (null != (node = thisLevel.poll())) {
 if (node.left != null) nextLevel.add(node.left);
 if (node.right != null) nextLevel.add(node.right);
 if (thisLevel.isEmpty()) {
 height++;
 Queue<TreeNode> swapTemp = thisLevel;
 thisLevel = nextLevel;
 // We could create a new nextLevel queue, but reusing the
 // newly emptied thisLevel queue is more efficient.
 nextLevel = swapTemp;
 }
 }
 }
 return height;
}

• JavaDeveloper: perfectly agreed, i hope some crazy interviewer does not see 2 data structures used as a disadvantage. It happens.
• JavaDeveloper: i do accept your code as a better answer, but for sake of interviews stick with 2 counters.
• 200_success: In almost all circumstances, priorities should be 1) bug-free, 2) easy to understand and maintain, and 3) efficient. An interviewer who insists on prioritizing (3) over (1) and (2) should be a red flag. They may be interviewing you as a candidate, but remember, you're evaluating them too as a potential employer.
• SwapnilS: @200_success well done. This code is really easy to understand.