#### Archived

This topic is now archived and is closed to further replies.

# Binary Tree space complexity?

This topic is 6063 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

##### Share on other sites
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.

Take home test?

1. 1
Rutin
23
2. 2
3. 3
JoeJ
20
4. 4
5. 5

• 29
• 40
• 23
• 13
• 13
• ### Forum Statistics

• Total Topics
631739
• Total Posts
3001957
×