Tree structure programming question help?

This is a discussion on Tree structure programming question help? within the C++ Programming forums, part of the General Programming Boards category; Hi, I am having trouble figuring this question out. Any help would be greatly appriciated. Thanks Give an O(n) time ...

  1. #1
    Registered User
    Join Date
    Feb 2008
    Posts
    43

    Tree structure programming question help?

    Hi,
    I am having trouble figuring this question out. Any help would be greatly appriciated. Thanks

    Give an O(n) time algorithm for computing the depth of all the nodes of a tree T, where n is the number of nodes of T.

  2. #2
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,274
    Quote Originally Posted by Rob4226 View Post
    Hi,
    I am having trouble figuring this question out. Any help would be greatly appriciated. Thanks

    Give an O(n) time algorithm for computing the depth of all the nodes of a tree T, where n is the number of nodes of T.
    I will not give the algorithm, but here's the thinking... To compute the depth of all nodes of a tree, you must obviously visit all of the nodes. This part of the algorithm is clearly O(n). To show that the entire algorithm is O(n), you must show that the act of computing the depth of any given node is O(1), or at least less than O(n). In fact, it is O(1).

    The best way to figure out the algorithm is to implement it. Write a small program which computes the depth of each node of a tree. If your program is worse than O(n), think about how to change it.

  3. #3
    Registered User
    Join Date
    Feb 2008
    Posts
    43
    What exactly is a O(n) time algorithm? Wouldnt the answer be that the time algorithm is O(n) because it takes O(1) time to visit each node and there are n nodes in tree T.

  4. #4
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,274
    Quote Originally Posted by Rob4226 View Post
    What exactly is a O(n) time algorithm? Wouldnt the answer be that the time algorithm is O(n) because it takes O(1) time to visit each node and there are n nodes in tree T.
    That's basically the entire argument, except that you need to explain more clearly why the time to compute the depth is O(1). The crux of the argument is, if you know the depth of a node A, then you know the depth of that node's children as well -- it's just the depth of A plus 1. Formalize that and you have a proof.

    The reality of it is exhibited in the code.

  5. #5
    Registered User
    Join Date
    Feb 2008
    Posts
    43
    Thank you for your help.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 06:59 PM
  2. 234 Tree question
    By dudeomanodude in forum C++ Programming
    Replies: 0
    Last Post: 04-03-2008, 04:34 PM
  3. BST delete again, but this time I think I'm close
    By tms43 in forum C++ Programming
    Replies: 9
    Last Post: 11-05-2006, 06:24 PM
  4. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  5. structure question
    By Unregistered in forum C Programming
    Replies: 5
    Last Post: 05-17-2002, 10:17 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21