Results 1 to 4 of 4
  1. #1
    peteryang22 is offline Member
    Join Date
    Apr 2011
    Posts
    2
    Rep Power
    0

    Default 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. #2
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    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. #3
    peteryang22 is offline Member
    Join Date
    Apr 2011
    Posts
    2
    Rep Power
    0

    Default

    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. #4
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    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 08:24 AM.

Similar Threads

  1. Replies: 0
    Last Post: 06-29-2010, 08:16 PM

Posting Permissions

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