CODEWITHSUNDEEP
pythonrecursiontree
Nuclearz
Nuclearz

Reputation: 25

Find the height and depth of a NOT BINARY TREEE in python

I know how to do it for binary tree but not for standard tree.

This doesn't works well and i don't understand what's wrong.

class Node:

 def __init__(self,V):
     self.id=V
     self.f=[]


def height(n):
    if n==None:
       return -1

    if n.f==None:
        return 0

    for x in n.f:
        return height(x)+1

Thank you for the help.

Upvotes: 0

Views: 113

Answers (1)

Mark
Mark

Reputation: 92440

You don't want to return in the for loop:

for x in n.f:
    return height(x)+1

That will just look at one item and return. Instead find the max value of the height of the children:

class Node:
    def __init__(self,V):
        self.id = V
        self.f = []

    def height(self):
        if len(self.f) == 0:
            return 1
        return max(x.height() + 1 for x in self.f)

n = Node(1)
n.f = [Node(10), Node(11), Node(12)]
n.f[0].f = [Node(20)]

n.height()
# 3

Upvotes: 1

Related Questions