Thread: 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.

Originally Posted by Rob4226

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.

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.

Originally Posted by Rob4226

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.

Thank you for your help.