CODEWITHSUNDEEP
pythontreebig-ocomplexity-theory
BarTM
BarTM

Reputation: 57

Time complexity with Tree data structure

i'm currently working on a Tree data structure in python. At the moment, i am trying to calculate subtree values, where a subtree value equals the largest value of a node in a given node's subtree. E.g. For the given tree:

       A(5)
       / \
     C(2) D(8)
      |
     B(10)

The subtree value of C would be 10, the subtree value of A would be 10 and the subtree value of D would be 8 etc. I am trying to reduce the complexity of the following code from O(n^2) to O(n). That is, im trying to move up the tree without using a nested loop. I have tried this with recursion but i am not too great at recursion hence the iterative solution below. Any help would be appreciated. Also, is it possible to do this without a recursive solution? 

         node = subtree_a
         while node.parent != None:
             children = node.parent.children
             for child in children:
                 if (child.subtree_value > node.parent.subtree_value):
                     node.parent.set_subtree_val(child.subtree_value)
             node = node.parent\

Upvotes: 0

Views: 525

Answers (1)

Blckknght
Blckknght

Reputation: 104712

A subtree's value only depends on the nodes lower than it on the tree, so there's absolutely no reason to have the bottom-up outer loop in your code.

A very simple top-down recursive approach would be:

def calc_subtree_value(node):
    val = node.value
    for child in node.children: # we don't need a base case, this forks for leaf nodes too
        calc_subtree_value(child)
        if child.subtree_value > val:
            val = child.subtree_value
    node.subtree_value = val

This takes O(N) time where N is the number of nodes in the subtree, as it visits each one exactly once. As I note in the comment, we don't need an explicit base case because the loop over the children does what we want (nothing) if there are no children to check for larger subtree values.

Upvotes: 1

Related Questions