CODEWITHSUNDEEP
pythonrecursiontreetuples
Z.Ken
Z.Ken

Reputation: 47

Find the height of tree, where the input tree can have any number of children

Part of my problem is to write a function that determines the height of a tree.

This is my current function,

def tree_height(node): 
  parent, children = node
  max_height = 0
  for child in children:
    height = tree_height(child)
    if height > max_height:
      max_height = height
  return max_height

but it only return 0.

* Note: There should only be one input parameter i.e node *

For,

tree = ("supercalifragilisticexpialidocious",(("a",(("b",(("candy",()),)),("onomatopoeia",()),)),("d",(("egg",(("f",()),)),)),))

output should be,

3

Upvotes: 1

Views: 189

Answers (2)

Diego Chinellato
Diego Chinellato

Reputation: 165

You never increase max_height, so the recursive calls will always return 0; remember that you are one step higher than your child.

def tree_height(node): 
    parent, children = node
    max_height = 0
    for child in children:
      child_height = tree_height(child)
      max_height = max(max_height, child_height +  1)
    return max_height

You need to "believe" in the recursion: assume that tree_height(child) gives you the height of your child. Then your height is simply the maximum height of all of your children plus one.

EDIT:

A more Pythonic code:

def tree_height(node):
  parent, children = node
  return max([tree_height(child) + 1 for child in children]) if children else 0

Upvotes: 2

StyleZ
StyleZ

Reputation: 1273

I think that you are on the right track, but the problem is that you probably dont understand the recursion height = tree_height(child) because if it doesnt have children it returns 0 which in the end will return 0 ( which is your case )

What you should do is that you put inside of the function another parameter which will count the depth

def tree_height(node, counter): 
    parent, children = node
    max_height = 0
    for child in children:
        height = tree_height(child, counter + 1)
        if height > max_height:
            max_height = height
    if max_height == 0:
        return counter
    return max_height

give this code a try and next time write / draw it on a paper to see what it is acctualy doing + dont post here your algorithmic homeworks :)

Upvotes: 0

Related Questions