(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

Give an algorithm for computing the depths of all the nodes of a tree T, where n is the number of nodes of T.

a) What is the complexity of your algorithm in terms of Big-O?

b) What is the best possible complexity that you believe can be achieved when solving such

problem? Explain why.

c) If your algorithm does not achieve this best complexity, can you design a better algorithm to

achieve such complexity? If so, give this algorithm as a second solution.

2. Relevant equations

The height of a node is the number of edges connecting it to the root node.

3. The attempt at a solution

I'm currently at the part before part a.

Is the following a complete (and 100% correct) algorithm, or is something missing?:

It feels "light" to me. Would this be accepted as a solution on an exam?Code (Text):

Algorithm nodeHeight(T,N,H)

Input: A binary tree T and a node N and height H of the given node

Output: The height of the given node in the given binary tree

if root node and node N are the same thing

return H

if there is a left node of N

nodeHeight(T,left node of N,H+1)

if there is a right node of N

nodeHeight(T,right node of N,H+1)

return 0

Any input in helping me fully understand how to answer this question would be GREATLY appreciated!

P.S.

Am I supposed to assume that the tree is a binary tree?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Algorithm for computing the depths of all the nodes of tree

Have something to add?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**