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;
}