Trying to implement tree and calculate it's height in python

Question

class node:
    parent=None
    data=None
    children=[]


def __init__(self, parent, data):
    self.data=data
    self.parent=parent


def set_parent(self, parent):
    self.parent=parent

def set_data(self, data):
    self.data=data

def create_node(parent, data):
    return node(parent, data)

class tree:
    nodes=[]
    root=node(None, None)

    def set_root(self, data, parent=None):
        self.root=node(parent, data)
        return self.root

    def get_root(self):
        return self.root

   def get_nodes(self):
        return self.nodes


def cal_height(Tree):
    h=[]
    if len(Tree.root.children)==0:
        return 1
    for child in Tree.root.children:
        t=tree()
        t.set_root(child.parent, child.data)
        height= 1+ cal_height(t)
        h.append(height)
    return max(h)




l1=input()
l=input().split()
Tree=tree()
for n, i in enumerate(l):
    if n==-1:
        Tree.nodes.append(Tree.set_root(i))

    else:
        Tree.nodes.append(create_node(n, i))

for p in Tree.nodes:
    for c in Tree.nodes:
        if p.data==c.parent:
            p.children.append(c)

for j in Tree.nodes:
    print(j.children)

I have been trying to create a tree and calculate it's height for an assignment. This is the code I've written so far but apparently, none of the children's nodes are being appended.

The input to the code is given as, for example- 4 -1 4 1 1

the index value with -1 is the root node, while the other inputs indicate that corresponding values are their parent nodes.

Answer 1

There are these issues in your code:

• children is defined as a class attribute, so whenever you look at j.children, it is always the same list that is shared by all nodes. Your class should not have any class attributes. For the data and parent attributes, you have also defined them as instance attributes, so there the problem does not occur. Fix as follows:

  class node:
      # removed class attributes
  
      def __init__(self, parent, data):
          self.data=data
          self.parent=parent
          self.children = []  # added
  

• The condition p.data==c.parent is never true, because it compares a string with a number. To avoid this, first convert the input list to a list of numbers at the start of your program:

  l = list(map(int, input().split()))
  

• enumerate will return a tuple with first the index, and then the value. You unpacked that tuple in the opposite way, and so the tree could never be built correctly. Change:

  for n, i in enumerate(l):
  

  to:

  for i, n in enumerate(l):
  

• The height for a leaf node should be 0, since the formal definition of height is the length of the longest path from the root to a leaf. The length of a path is expressed in the number of edges. As there is no edge in a tree with just one node, the height should be 0 for such a node.

  So:

  if len(Tree.root.children)==0:
      return 0  # not 1
  

• cal_height goes wrong when it sets a new root with this statement:

  t.set_root(child.parent, child.data)
  

  Here you make a node that has no children! So even if child had children, they will not be considered. The recursive call to cal_height will not bring anything useful now: it will always return 1.

• cal_height shouldn't need to create new tree and node instances. You already have the tree, and this function should not need to change anything to it. It should be a read-only operation.

  This function needs to be completely reviewed. I propose this:

  def cal_height(Tree):
  
      def height(node):
          if not node:
              return -1
          return 1 + max(map(height, node.children), default=-1)
  
      return height(Tree.root)
  

With these changes it will work.

Without tree

You actually don't need to create a tree or nodes at all. This can be done with a mere list that logs the depth of each node. If from each node (index) you follow the parent references until you encounter -1, then you really walk up the tree and know the depth of the original node you started from. By registering the depths for all the nodes along the way you can avoid traveling the same subpaths over and over again. The node that has the greatest depth, has a depth that is equal to the height of the tree.

Spoiler solution:

def get_height(parents): depths = [-1] * len(parents) def get_depth(i): if i == -1: return -1 if depths[i] == -1: depths[i] = 1 + get_depth(parents[i]) return depths[i] for i in range(len(parents)): get_depth(i) return max(depths) n = input() parents = list(map(int,input().split())) height = get_height(parents) print(height)