1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Algorithm for computing the depths of all the nodes of tree

  1. Nov 13, 2017 #1

    s3a

    User Avatar

    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?:

    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
     
    It feels "light" to me. Would this be accepted as a solution on an exam?

    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?
     
  2. jcsd
  3. Nov 13, 2017 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I'm afraid there are a couple of things I do not understand about your algorithm.
    First, the task is to find the depth of all nodes, not just one. If your idea is to then run this algorithm for each node in the tree tvat seems very inefficient.
    Secondly, it seems to be running the wrong way. If you want the depth of a node, don't you need to work towards the root, and that would involve running the parent line, not the two child lines, no?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted