Thread: need help with big O notations

1. Member
Join Date
Apr 2011
Posts
2
Rep Power
0

need help with big O notations

just wondering what is the big O cost for finding the number of leaf nodes in a binary tree, and what is the big O for find the sum of all the values in a binary tree

2. No one is going to give you the answer. I'm assuming this assignment is homework. Have you done anything to try to figure this out yourself yet?

3. Member
Join Date
Apr 2011
Posts
2
Rep Power
0
Just wanted to see if I'm correct or not, from my understanding accessing a node in a binary tree takes o(logn) time. So does this mean that to get all of the leaf nodes in a tree is just o(logn) then. And for getting the sum of all the numbers in a binary tree should be o(n) right? Since we are iterating through every node in the tree and adding the values together.

4. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,565
Rep Power
12
Also posted at OTN

It may help to think about what counting the nodes and finding the sum have in common. COunting adds 1 every time it finds a node while the sum calculation involves adding the node's value. From a complexity point of view they are pretty much the same thing.
Last edited by pbrockway2; 04-09-2011 at 09:24 AM.

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•