How to do tree traversal?

Question

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?

Think carefully about what happens when the recursion reaches a leaf of the tree. Is self equal to None? Therefore, will the code in the if block run? Therefore, will the recursive calls be attempted? Now - is self.left and/or self.right equal to None? (Hint: how is a leaf defined?) Therefore, what will happen if a recursive call is attempted on that value? — Karl Knechtel
– Karl Knechtel, Commented Apr 17, 2022 at 6:20

OTheDev · Accepted Answer · 2022-04-17 06:16:44Z

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.

Thanks for your answer. I see this now actually. I was having an issue trying to understand it at first but of course None will not have an inOrder()

Collectives™ on Stack Overflow

How to do tree traversal?

1 Answer 1

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Related