CODEWITHSUNDEEP
pythonbinary-search-tree
Unknown
Unknown

Reputation: 676

Searching both sides of a Binary Search Tree in Python

I have a BST in python, with each node holding 3 pieces of data. Those pieces of data being ID, Mark, and Name.

What I'm trying to do is search for a Name, but the nodes are based on IDs, this is how I've searched. The function is supposed to output the ID of the specific Name. 

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

Unfortunately I'll only ever be searching the left side of the Tree, and not the right, the opposite applies if I search the right side first.

How do I search both sides for this?

Upvotes: 1

Views: 634

Answers (5)

Will Cheng
Will Cheng

Reputation: 199

try this: 

def search(node, name):
    self_result = [node['id']] if node['name'] == name else []
    if not node['left'] and not node['right']:
        return self_result
    elif node['left'] and not node['right']:
        return self_result + search(node['left'], name)
    elif not node['left'] and node['right']:
        return self_result + search(node['right'], name)
    else:
        return self_result + search(node['left'], name) + search(node['right'], name)

test_tree = {'id':0, 'name': 'a', 
             'left': {'id':1, 'name': 'a', 
                      'left':{'id':3, 'name':'c', 
                              'left':{'id':4,'name': 'd', 
                                  'left' : None,
                                  'right' : None},
                          'right':None},
                  'right':{'id':4, 'name':'e',
                           'left': None,
                           'right': None}
                  }, 
             'right': {'id':5, 'name':'c',
                       'left': {'id':6, 'name':'e',
                                'left': None,
                                'right': None},
                       'right': {'id': 7, 'name': 'a',
                                 'left' : {'id' : 8, 'name': 'b',
                                           'left': None,
                                           'right' : None},
                                 'right' : None
                                }
                      }
            }

if __name__ == '__main__':
    assert search(test_tree, 'a') == [0, 1, 7]
    assert search(test_tree, 'b') == [8]
    assert search(test_tree, 'c') == [3, 5]
    assert search(test_tree, 'e') == [4, 6]
    print 'ok'

It can also deal with multiple matches.

Upvotes: 0

John La Rooy
John La Rooy

Reputation: 304137

You could traverse the branches like this if you wish to avoid the extra recursive call. Note that it is preferable to test identity of None rather than equality

for branch in ('left', 'right'):
    if tree[branch] is not None:
        result = findName(tree[branch], name)
        if result is not None:
            return result

Upvotes: 0

Jim Garrison
Jim Garrison

Reputation: 86774

...
result = findName(tree['left'],name)
if result is None:
    result = findName(tree['right'],name) 
return result

Upvotes: 2

twain249
twain249

Reputation: 5706

The problem is you are returning in the 

if tree['left']!=None:
    return findName(tree['left'],name)

What you have to do is create a local variable and set it to the value from findName() then if you get None continue with the right otherwise return the value.

Upvotes: 0

Niklas B.
Niklas B.

Reputation: 95298

You shouldn't return if you're not yet finished! Instead, you can replace your last 4 lines with a single, short-circuiting or:

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

Make sure your IDs don't include 0, though, otherwise this method will fail because 0 is a falsy value, just like None.

Upvotes: 5

Related Questions