21

First of all, I swear this is not homework, it's a question I was asked in an interview. I think I made a mess of it (though I did realise the solution requires recursion). Here is the question:

Implement the count() method which returns the number of nodes in a tree. If a node doesn't have either a left or right child, the relevant getXXChild() method will return null

class Tree {

  Tree getRightChild() {
    // Assume this is already implemented
  }

  Tree getLeftChild() {
    // Assume this is already implemented
  }

  int count() {
    // Implement me
  }
}

My reason for asking the question is simply curious to see the correct solution, and thereby measure how bad mine was.

Cheers, Tony

6
  • 2
    // No.. you didn't say please Feb 13, 2009 at 21:01
  • @Tony Can you post whatever solution you came up with? It might be of more value to you if we point problems with your design rather than just throwing the correct answer out there.
    – Tim Frey
    Feb 13, 2009 at 21:07
  • If this is an interview question, the interviewer probably not only wants to see 'the code' (many fine solutions posted) but also a discussion of recursion versus iteration (see e.g. David Hanak's answer) and stack versus heap.
    – Brian
    Feb 13, 2009 at 21:20
  • int numberOfRightKids = getRightChild() != null ? getRightChild().count() : 0; int numberOfLeftKids = getLeftChild() != null ? getLeftChild().count() : 0 int me = 1; return numberOfLeftKids + numberOfRightKids + me; Feb 13, 2009 at 22:05
  • Java doesn't have a Functor interface? LOL.
    – jrockway
    Feb 14, 2009 at 0:46

15 Answers 15

32
int count() {
  Tree right = getRightChild();
  Tree left = getLeftChild();
  int c = 1;                                      // count yourself!
  if ( right != null ) c += right.count();        // count sub trees
  if ( left != null ) c += left.count();          // ..
  return c;
}
1
  • 1
    Edited "return count" to "return c". :-) Feb 13, 2009 at 20:57
19

A trivial recursive solution:

int count() {
   Tree l = getLeftTree();
   Tree r = getRightTree();
   return 1 + (l != null ? l.count() : 0) + (r != null ? r.count() : 0);
}

A less trivial non-recursive one:

int count() {
    Stack<Tree> s = new Stack<Tree>();
    s.push(this);
    int cnt = 0;
    while (!s.empty()) {
        Tree t = s.pop();
        cnt++;
        Tree ch = getLeftTree();
        if (ch != null) s.push(ch); 
        ch = getRightTree();
        if (ch != null) s.push(ch); 
    }
    return cnt;
}

The latter is probably slightly more memory-efficient, because it replaces recursion with a stack and an iteration. It's also probably faster, but its hard to tell without measurements. A key difference is that the recursive solution uses the stack, while the non-recursive solution uses the heap to store the nodes.

Edit: Here's a variant of the iterative solution, which uses the stack less heavily:

int count() {
    Tree t = this;
    Stack<Tree> s = new Stack<Tree>();
    int cnt = 0;
    do {
        cnt++;
        Tree l = t.getLeftTree();
        Tree r = t.getRightTree();
        if (l != null) {
            t = l;
            if (r != null) s.push(r);
        } else if (r != null) {
            t = r;
        } else {
            t = s.empty() ? null : s.pop();
        }
    } while (t != null);
    return cnt;
}

Whether you need a more efficient or a more elegant solution naturally depends on the size of your trees and on how often you intend to use this routine. Rembemer what Hoare said: "premature optimization is the root of all evil."

5
  • This won't compile with Java. Unfortunately, you need to explicitly test if something == null, so you need l== null and r == null here.
    – Tim Frey
    Feb 13, 2009 at 20:56
  • Thanks! It was some time ago I actively used Java. Feb 13, 2009 at 21:03
  • How about allowing nulls to be pushed onto the stack, but only incrementing the counter if the object popped off is not null. You can remove 1 if statement this way, and also you can then do s.push(getLeft()) and s.push(getRight())
    – Tim Frey
    Feb 13, 2009 at 21:06
  • I beleive that would be slightly more expensive on the CPU (extra push/pop), but its definitely an option, and, like you said, one line fiewer. :-) Feb 13, 2009 at 21:09
  • I thought it was Knuth who said that! :) Jun 15, 2012 at 17:33
11

I like this better because it reads:

return count for left + count for rigth + 1

  int count() {
      return  countFor( getLeftChild() ) + countFor( getRightChild() ) + 1;
  }
  private int countFor( Tree tree )  { 
       return tree == null ? 0 : tree.count();
  }

A little more towards literate programming.

BTW, I don't like the getter/setter convention that is so commonly used on Java, I think a using leftChild() instead would be better:

  return countFor( leftChild() ) + countFor( rightChild() ) + 1;

Just like Hoshua Bloch explains here http://www.youtube.com/watch?v=aAb7hSCtvGw at min. 32:03

If you get it rigth your code reads...

BUT, I have to admit the get/set convention is now almost part of the language. :)

For many other parts, following this strategy creates self documenting code, which is something good.

Tony: I wonder, what was your answer in the interview.

2
  • -1 points on going against the JavaBean idiom, which has proven hugely useful. (I upscored you anyway!) Feb 21, 2009 at 11:24
  • @oxbow: Yeap, the Java bean model never got the desired effect ( which was to have truly standalone beans ) but the idiom was been very beneficial, specially in webdevelopment.
    – OscarRyz
    Feb 21, 2009 at 19:06
4
return (getRightChild() == null ? 0 : getRightChild.count()) + (getLeftChild() == null ? 0 : getLeftChild.count()) + 1;

Or something like that.

4
  • I wouldn't write this as a one-liner in practice but the fact that you can makes a point about the simplicity... +1
    – David Z
    Feb 13, 2009 at 21:02
  • Why not? Can't beat a bit of ternary abuse :-) Feb 13, 2009 at 21:02
  • If you wrote that during an interview, i would be annoyed not impressed.
    – Kip
    Feb 13, 2009 at 21:14
  • @Kip Not as annoyed as I would be if I ended up in a Java interview :-) Feb 13, 2009 at 21:22
4

Something like this should work:

int count()
{
    int left = getLeftChild() == null ? 0 : getLeftChild().count();
    int right = getRightChild() == null ? 0 : getRightCHild().count();

    return left + right + 1;
}
4
  • Remember to count yourself :P
    – Blorgbeard
    Feb 13, 2009 at 20:57
  • Pfft what are you guys talking about, I always added 1 ;-) Thanks!
    – Tim Frey
    Feb 13, 2009 at 20:57
  • Who said count should return null? The problem says "The relevant method" so it is referring to the "leftNode/rightNode". That was your point or a missed something?
    – OscarRyz
    Feb 13, 2009 at 21:03
  • I too thought he meant the count() method should return null if there are no child nodes. It wasn't clear until the second reading. When he said "relevant method", I assumed he meant the method relevant to this question.
    – Kip
    Feb 13, 2009 at 21:10
4
class Tree {

  Tree getRightChild() {
    // Assume this is already implemented
  }

  Tree getLeftChild() {
    // Assume this is already implemented
  }

  int count() {
   return 1 
      + getRightChild() == null? 0 : getRightChild().count()
      + getLeftChild() == null? 0 : getLeftChild().count();
  }
}
2

You can count the tree by traversing it many ways. Simply preorder traversal, the code would be (based on the functions you defined):

int count() {
    count = 1;
    if (this.getLeftChild() != null)
        count += this.getLeftChild().count();
    if (this.getRightChild() != null)
        count += this.getRightChild().count();
    return count;
}
2

Implement the method:

public static int countOneChild(Node root)
{
    ...
}

that counts the number of internal nodes in a binary tree having one child. Add the function to tree.java program.

1

I did it by preorder recurssion. Altough it doesn't exactly follow the interview format by using localRoot, but I think you get the idea.

private int countNodes(Node<E> localRoot, int count) {
    if (localRoot == null) 
        return count;     
    count++; // Visit root
    count = countNodes(localRoot.left, count); // Preorder-traverse (left)
    count = countNodes(localRoot.right, count); // Preorder-traverse (right)
    return count;
}

public int countNodes() {
   return countNodes(root, 0);
}
0

This is a standard recursion problem:

count():
    cnt = 1 // this node
    if (haveRight) cnt += right.count
    if (haveLeft)  cnt += left.count
return cnt;

Very inefficient, and a killer if the tree is very deep, but that's recursion for ya...

2
  • but that's as efficient as it gets, without caching higher-level counts, right?
    – Kip
    Feb 13, 2009 at 21:12
  • The algorithm is fine, it just doesn't really answer the original question. Plus, haveLeft and haveRight, while obvious, aren't declared here.
    – Tim Frey
    Feb 13, 2009 at 21:19
0
int count()

{
   int retval = 1;
    if(null != getRightChild()) retval+=getRightChild().count();
    if(null != getLeftChild()) retval+=getLeftChild().count();
    return retval;

}

God I hope I didn't make a mistake.

EDIT: I did actually.

2
  • Your if statements need to explicitly check == null, otherwise this won't work for Java.
    – Tim Frey
    Feb 13, 2009 at 21:00
  • Yep, recalled that when I posted :)
    – mannicken
    Feb 13, 2009 at 21:01
0

Of course, if you want to avoid visiting every node in your tree when you count, and processing time is worth more to you than memory, you can cheat by creating your counts as you build your tree.

  1. Have an int count in each node, initialized to one, which respresents the number of nodes in the subtree rooted in that node.

  2. When you insert a node, before returning from your recursive insert routine, increment the count at the current node.

i.e.

public void insert(Node root, Node newNode) {
  if (newNode.compareTo(root) > 1) {
    if (root.right != null) 
      insert(root.right, newNode);
    else
      root.right = newNode;
  } else {
    if (root.left != null)
      insert(root.left, newNode);
    else
      root.left = newNode;
  }
  root.count++;
}

Then getting the count from any point just involves a lookup of node.count

0

My first attempt didn't have anything new to add, but then I started to wonder about recursion depth and whether it would be possible to rearrange the code to take advantage of the tail call optimization feature of the latest Java compiler. The main problem was the null test - which can be solved using a NullObject. I'm not sure if TCO can deal with both recursive calls, but it should at least optimize the last one.

static class NullNode extends Tree {

    private static final Tree s_instance = new NullNode();

    static Tree instance() {
        return s_instance;
    }

    @Override
    Tree getRightChild() {  
        return null;
    }  

    @Override
    Tree getLeftChild() {  
        return null;
    }  

    int count() {  
        return 0;
    }
}

int count() {      
    Tree right = getRightChild();      
    Tree left  = getLeftChild();      

    if ( right == null ) { right = NullNode.instance(); }
    if ( left  == null ) { left  = NullNode.instance(); }

    return 1 + right.count() + left.count();
}   

The precise implementation of NullNode depends on the implementations used in Tree - if Tree uses NullNode instead of null, then perhaps the child access methods should throw NullPointerException instead of returning null. Anyway, the main idea is to use a NullObject in order to try to benifit from TCO.

2
  • You have to do more processing on the result of each of the count calls before returning (adding them to the return register's current value), so I don't think you have a proper tail call here. :-( Aug 5, 2010 at 19:33
  • Platinum Azure: Thanks for the comment. It looks like a fatal flaw in my idea. If TCO can't deal with the accumulation in the return value then I guess I need a better optimization :-(
    – richj
    Aug 5, 2010 at 20:02
0

Questions related to binary tree should be expected in an interview. I would say to take time before any next interview and go through this link. There are about 14 problems solved .You can have a look and how the solution is done. This would give you an idea of how to tackle a problem with binary tree in future.

I know your question is specific to the count method .That is also implemented in the link that i provided

0
class Tree {

  Tree getRightChild() {
    // Assume this is already implemented
  }

Tree getLeftChild() {
    // Assume this is already implemented
 }

 int count() {
    if(this.getLeftChild() !=null && this.getRightChild()!=null) 
        return 1 + this.getLeftChild().count() + this.getRightChild().count();
    elseif(this.getLeftChild() !=null && this.getRightChild()==null)
        return 1 + this.getLeftChild().count();
    elseif(this.getLeftChild() ==null && this.getRightChild()!=null)
        return 1 + this.getRightChild().count();
    else return 1;//left & right sub trees are null ==> count the root node
  }
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.