need help with big O notations

**peteryang22** · 04-09-2011, 04:11 AM

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

**sunde887** · 04-09-2011, 05:16 AM

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?

**peteryang22** · 04-09-2011, 06:51 AM

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.

**pbrockway2** · 04-09-2011, 08:18 AM

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.