Binary Search Trees and Data with Python

Question

I have a binary tree function with 3 pieces of data in each node. They are classified by id numbers. They also hold "Name" and "Mark"

A certain function I'm having problem with is a name searching function, it looks like this:

def findName(tree,name):
 if tree==None:
 return None
 elif tree['name']==name:
 return True
 else:
 findName(tree['right'],name)
 findName(tree['left'],name)

I can always find the first name in a tree, but i can't find any onwards. If I input findName(tree['right'],name) in the python idle I get true if the name is in the tree.

Answer 1

the only way for a function to actually return some data, is if it itself uses a return statement. Your else: suite doesn't contain any return statements.

• Unknown: First off I love the username. :P and Yeah I assumed that since it was recursive it would be returning the True. Thank you.

Answer 2

on the else you would have to do something like:

return findName(tree['right'],name) or findName(tree['left'],name)

so that it searches in both branches and if it finds it in any of those branches the return value will be True

Answer 3

I believe there are opensource binary search tree modules available; if your goal is to learn about BST's, by all means write your own, but if you're working on something that is amenable to opensource, you might want to try a canned module that's already been tested and debugged.

I have something kind of like a BST for Python at http://stromberg.dnsalias.org/~strombrg/treap/ . It's actually a variant of a BST that doesn't require keys to be fed to the BST in a random order - it uses a random value on each node to scatter things. To the programmer, it looks like a dictionary except the keys come back sorted when you iterate over them, and lookups aren't as fast as a dictionary (hash).

Treaps were discovered back in the late 80's, I believe, so they're a relatively recent bit of CS. They're a very well-rounded datastructure; the more different ways you access the same data, the better off you are likely to be with a treap.

Actually, from what you've described, you might even be better served by just a dictionary (hash table) where the keys are your names.