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!

Answer 1

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)