5
\$\begingroup\$

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;
}
\$\endgroup\$
6
\$\begingroup\$

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;
}
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ perfectly agreed, i hope some crazy interviewer does not see 2 data structures used as a disadvantage. It happens. \$\endgroup\$ – JavaDeveloper Sep 29 '13 at 1:45
  • \$\begingroup\$ i do accept your code as a better answer, but for sake of interviews stick with 2 counters. \$\endgroup\$ – JavaDeveloper Sep 29 '13 at 1:46
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – 200_success Sep 29 '13 at 2:20
  • \$\begingroup\$ @200_success well done. This code is really easy to understand. \$\endgroup\$ – SwapnilS Aug 4 '14 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.