Amazon.com

  www.amazon.com
Work in HR? Unlock Free Profile

Amazon.com Software Development Engineer Interview Question

I interviewed in Seattle, WA and was asked:
"make a function that counts the number of nodes in a tree"
Add Tags [?]
Answer

Part of a Software Development Engineer Interview Review - one of 4,652 Amazon.com Interview Reviews

Answers & Comments

0
of 2
votes
use a queue
- Interview Candidate on Jan 13, 2013
3
of 3
votes
Use recursion, it's the best at problems like this! Think of the problem in these terms:

1.) An empty tree has 0 nodes
2.) Any other tree has one root node, plus however many nodes are in the left and right sub-trees.

Now think of how to put that into code.
- Anonymous on Jan 15, 2013
0
of 0
votes
A non-recursive approach is to perform a breadth-first traversal and and count the nodes as you visit them.

Specifically, suppose we have a class of type Node that contains two fields, called left and right, both of type Node. Let root (of type Node) be the root of the tree. Here's the code, which you would invoke with the call: nNodes = countNodes( root );

public int countNodes( Node node ) {
    int count = 0;
    Queue<Node> q = new LinkedList<Node>();
    if ( node != null ) {
        q.add( node );
    }
    while ( !q.isEmpty() ) {
        count += 1;
        Node traveler = q.remove();
        if ( traveler.left != null ) {
            q.add( traveler.left );
        }
        if ( traveler.right != null ) {
            q.add( traveler.right );
        }
    }
    return count;
}

Hope this is useful!
- Peter JL on Mar 3, 2013

To comment on this question, Sign In with Facebook or Sign Up

Tags are like keywords that help categorize interview questions that have something in common.