I have written a method in java - int itemcount(BinaryTree s, Object item) which returns the amount of occurences of 'item' in the binary tree 's'. From looking at this do any of you know what the space complexity of this recursive method would be? static int itemcount(BinaryTree s, Object item) throws TreeEmptyException {//method to count amount of occurences of item in s if(s.isempty()) return 0;//no occurences else { if(item.equals(s.nodevalue()))//1 occurence return 1 + itemcount(s.lefttree(),item) + itemcount(s.righttree(),item); else return itemcount(s.lefttree(),item) + itemcount(s.righttree(),item); } }//itemcount Edited by - blue_harvester on December 10, 2001 6:00:04 PM Edited by - blue_harvester on December 10, 2001 6:03:39 PM

First of all, it allocates no memory, so the recursive depth is the only memory used. Second, you''ll notice it traverses only downward, and only along one path at a time, meaning that it will never have a recursive depth greater than the number of nodes in the tree. So an absolute upper bound is O(n). However, it''s going to be O(h), which in general will be much better than O(n), especially if any balancing is done. There''s also a lower bound of O(lg n), which is also the average case any time it''s kept somewhat balanced.