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

Printable View

- 04-09-2011, 04:11 AMpeteryang22need 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

- 04-09-2011, 05:16 AMsunde887
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?

- 04-09-2011, 06:51 AMpeteryang22
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.

- 04-09-2011, 08:18 AMpbrockway2
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.