pythontree-traversalinorder

How to do tree traversal?


So I am running into some issue that has left me dumbfounded. I do not understand where I am going wrong with my code but the idea I have is I check if the current node I am at is None and if it is then I return a list of my tree in in order, pre order, and post order. Here is my code:

class Node:
  def __init__(self, data):
    self.data = data
    self.left = None
    self.right = None

  def inOrder(self, arr=[]):
    if self is not None:
      self.left.inOrder(arr)
      arr.append(self.data)
      self.right.inOrder(arr)

    return arr

When I run it I get an error of self.left.inOrder() AttributeError: 'NoneType' object has no attribute 'inOrder' which I have not idea as to why. I am checking that self is not None so shouldn't this guarantee my Node to have a left and right.

I am only showing the inOrder I have implemented.

I have solved this instead by doing the following

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def inOrder(self):
        if self is not None and self.left is not None:
            self.left.inOrder()

        print(self.data)

        if self is not None and self.right is not None:
            self.right.inOrder()


root = Node(1)
root.left = Node(2)
root.right = Node(3)


root.inOrder()

Whether I save it to a list or just print it is fine with me but if I already check if self is not None then shouldn't I be able to call self.left.inOrder and self.right.inOrder?


Solution

  • self is not None. self refers to an instance of the class. self.left is an instance attribute that you set to None in your __init__() method when you create the instance. Because self.left refers to None and the object None does not have the inOrder() method, you obtain an AttributeError. Within your class definition, self (referring to an instance of the class) does have the inOrder() method, but it's attribute self.left (referring to None), does not.