How can I make my Binary Tree's search/traversal method work?

Question

I just recently got done with my own implementation of a binary tree, which works pretty well for a first attempt I think. I can add left and right children to a root node fairly easily, view a node's value, as well as verify if a certain node is a child or not.

However, I do have a problem with a search function I have, which calls upon a Pre-order traversal system. In my IDE, using a binary tree like so:

Simple Binary Tree

attempting to use my search function constantly returns the error "AttributeError: 'int' object has no attribute 'data'", which I'm not particularly sure what it means. In my code here:

def search(self, value):
 def find(x):
 if x.data is not False:
 return True
 val2 = self.traverse_pre_order(find)
 if val2 is not True:
 return False
 else:
 return True

I attempted to change x.data to simply x, but this returns me the AttributeError 'NoneType' object has no attribute 'traverse_pre_order'.

I've attatched a link to PasteBin with my full code relevant to the Binary Tree I'm working on.

Answer 1

First of all, x.data should be changed to x since you do visit(self.data). Your input is already self.data, so x would be self.data and x.data would be equal to self.data.data, which doesn't make sense.

Second, you should change your recursion condition in traverse_pre_order. It should be if self.left is not None: not if hasattr(self, 'left'):. You don't want to check if self.left exists (since it will always exist because you initialize it in __init__). Instead you should check if it is None.

There are also noticeable errors in structure of your traverse_pre_order and search but I guess you can try solving that yourself first.

Answer 2

A few issues with your code:

• you define some variables right below the class definition (value, left_child, right_child), but never use them.

• Clearly think about what each method should do. Your traverse_pre_order function doesn't return anything, so nothing is stored in val2 in the search function.

You get the errors

1. because you basically call find(Node.data), and the find function then tries to do data.data (which doesn't exist)

2. because at the end there is a node with left=None and you try to call left.traverse_pre_order(). You should check left not None instead of using hasattr