current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 4 down vote favorite

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;
}
share|improve this question
up vote 4 down vote accepted

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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