Recursive Binary Search Tree Insertion

Question

I'm getting errors when I'm trying to insert multiple values into my tree. I'd like it to be able to fill multiple of the available leafs on various levels of the tree. Here is my code:

tree = {
    'key' : 'root',
    'left': {
        'key': 'something',
        'left': None, 
        'right': {
            'key': 'something',
            'left': {
                'key': 'somthing', 
                'left': None, 
                'right': None
            }, 'right': {
                'key': 'something',  
                'left': None, 
                'right': None
            }
        }
    }, 'right': {
        'key': 'something',
        'left': {
            'key': 'Something',
            'left':
            {
                'key': 'something', 
                'left': None, 
                'right': None
            }, 'right': None
        }, 'right': {
            'key': 'something',  
            'left': None, 
            'right': None
        }
    }
}

def insert(tree, k):
    if tree['key'] == None:
        tree['key'] = k
    else:
        if tree['key'] > k:
            if tree['left'] == None:
                tree['left'] = k
            else:
                insert(tree['left'], k)

        if tree['key'] < k:
            if tree['right'] == None:
                 tree['right'] = k
            else:
                insert(tree['right'], k)

insert(tree, "hello")
insert(tree, "data science")

The error I'm getting looks like this:

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-114-d826085e4673> in <module>()
     71 
     72 insert(tree, "hello")
---> 73 insert(tree, "data science")
     74 #insert(tree, "jerry")
     75 #insert(tree, "apple")

<ipython-input-114-d826085e4673> in insert(tree, k)
     59                 tree['left'] = k
     60             else:
---> 61                 insert(tree['left'], k)
     62 
     63         if tree['key'] < k:

<ipython-input-114-d826085e4673> in insert(tree, k)
     59                 tree['left'] = k
     60             else:
---> 61                 insert(tree['left'], k)
     62 
     63         if tree['key'] < k:

<ipython-input-114-d826085e4673> in insert(tree, k)
     52 
     53 def insert(tree, k):
---> 54     if tree['key'] == None:
     55         tree['key'] = k
     56     else:

TypeError: string indices must be integers

I don't quite understand the error above. I believe I'm comparing the value of the tree key to another value, but I don't know why it's asking for an integer. Any help would be much appreciated.

Thanks!

BTW, it's usual to do None tests with is rather than ==. It's safe to use the identity test like that because there's only one None object. — PM 2Ring
– PM 2Ring, Commented Oct 28, 2017 at 6:50

kgf3JfUtW · Accepted Answer · 2017-10-28 06:38:06Z

Your base case should be {"key" : k, "left" : None, "right" : None} instead of just k.

Since you defined each node in the tree to be a dictionary, you have to respect this data structure at all times.

Otherwise, after your first insertion, the string "hello" becomes a node, which is already incorrect. Then, when you attempt to do a second insertion, the insert function will be called on a "node" that is really a string.

def insert(tree, k):
    if tree['key'] == None:
        tree['key'] = {"key":k, "left":None, "right":None }
    else:
      # should insert on left
        if tree['key'] > k:
            if tree['left'] == None:
                tree['left'] = {"key":k, "left":None, "right":None }
            else:
                insert(tree['left'], k)
      # should insert on right
        if tree['key'] < k:
            if tree['right'] == None:
                 tree['right'] = {"key":k, "left":None, "right":None }
            else:
                insert(tree['right'], k)

Collectives™ on Stack Overflow

Recursive Binary Search Tree Insertion

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related