0

I'm trying to build a BST (binary search tree) with dict in python. I do not understand why my code is not adding nodes to the BST. I saw a similar post here: How to implement a binary search tree in Python? which looks the same as my code except declaring a node class, but I would like to know why my dict implementation fails (and hopefully improve my understanding of parameter passing with recursion in python).

keys = [10,9,2,5,3,7,101,18]
start = {'key': keys[-1], 'val': 1, 'left': None, 'right': None}
def binarySearch(root, node):
# compare keys and insert node into right place
    if not root:
        root = node
    elif node['key'] < root['key']:
        binarySearch(root['left'], node)
    else:
        binarySearch(root['right'], node)

# Now let's test our function and build a BST
while keys:
    key = keys.pop()
    node = {'key': key, 'val': 1, 'left': None, 'right': None}
    binarySearch(start, node)
print(start) # unchanged, hence my confusion. Thx for your time!

===========================================

Edit: here is the code that would make it work!

def binarySearch(root, node):
# compare keys and insert node into right place
    if not root:
        root = node
    elif node['key'] < root['key']:
        if not root['left']: root['left'] = node
        else: binarySearch(root['left'], node)
    else:
        if not root['right']: root['right'] = node
        else: binarySearch(root['right'], node)

Here is what I think that is happening under the hood (why one version is able to add to BST but the other one is not):

In the original version, we will reach a recursion call where root still points to None inside the BST, but then root = node make root points to node which has absolutely no connection with start, i.e. the BST itself. Then local variables are deleted and no changes are made.

In the modified version, we will avoid this since when we add the node by e.g. root['left'] = node. Here root is still pointing to the original BST and thus we are modifying the key-val pair in the original BST instead of having root point to something totally outside the BST.

mathematica_abstracto
  • 33
  • 1
  • 5

2 Answers2

1

Let's run through your code as though we were the python interpreter.

Lets start at the first call: binarySearch(start, node)

Here start is the dict defined at the top of your script and node is another dict (which curiously has the same value).

Lets jump inside the call and we find ourselves at: if not root: where root refers to start above and so is truthy so fails this if.

Next we find ourselves at: elif node['key'] < root['key']: which in this case is not True.

Next we pass into the else: and we are at: binarySearch(root['right'], node).

Just before we jump into the first recursive call, lets review what the parameters to the call are: root['right'] from start has the value None and node is still the same dict which we want to insert somewhere. So, onto the recursive call.

Again we find ourselves at: if not root:

However this time root just refers to the first parameter of the first recursive call and we can see from the above review of the parameters that root refers to None.

Now None is considered falsy and so this time the if succeeds and we are on to the next line.

Now we are at root = node.

This is an assignment in python. What this means is that python will use the variable root to stop referring to None and to refer to whatever node currently refers to, which is the dict which was created in the while loop. So root (which is just a parameter, but you can think of as a local variable now) refers to a dict.

Now what happens is that we are at the end of the first recursive call and this function ends. Whenever a function ends, all the local variables are destroyed. That is root and node are destroyed. That is just these variables and not what they refer to.

Now we return to just after the first call site i.e. just after binarySearch(root['right'], node)

We can see here that the parameters: root['right'], node still refer to whatever they were referring to before. This is why your start is unchanged and why your program should deal with left and right now instead of recursing.

quamrana
  • 37,849
  • 12
  • 53
  • 71
  • Thanks a lot for your clear explanation! May I ask how to modify the code so that one could successfully insert the node into the ```start``` outside the function? – mathematica_abstracto Jun 07 '20 at 17:48
  • Well, as I commented before, its there in the accepted answer of the linked question. – quamrana Jun 07 '20 at 17:49
  • Right... I did make it work and added it to the post. But if I understood your answer correctly when it passes ```root['left']``` into the recursive call, it will still assign ```root``` to point to ```root['left']``` as a local variable to be destroyed by the end of that recursion call. So we are never going to be able to make changes beyond first recursion? – mathematica_abstracto Jun 07 '20 at 18:19
  • I'm referring to the part 'Now what happens is that we are at the end of the first recursive call and this function ends. Whenever a function ends, all the local variables are destroyed. That is root and node are destroyed. That is just these variables and not what they refer to.' – mathematica_abstracto Jun 07 '20 at 18:20
  • Your `while keys:` loop (which should be `for key in keys:` btw) keeps feeding new `node`s into `binarySearch()` (which should be `binaryInsert()` btw) so at some point both `left` and `right` of `start` will have their own `node`s. Then at the next call there will be an `else: binarySearch(...)` which passes one of the previously added `node`s in, which becomes `root` and then there is the possibility of that `node` being modified, just as `start` was. – quamrana Jun 07 '20 at 19:08
  • Thanks! I think I understand what you mean now and I've added that to the post (I'd appreciate it if you could just confirm if my logic is right). And yeah I would use for loop except in the script above I'm poping the keys, so while loop will terminate and do the same job. – mathematica_abstracto Jun 07 '20 at 19:41
-1
#Creted by The Misunderstood Genius
def add_root(e,key):
    ''''
     e is node's name
    key is the node's key search
    '''
    bst=dict()
    bst[e]={'key':key,'P':None,'L':None,'R':None}
    return bst
def root(tree):
   for k,v in tree.items():
       if v['P'] == None:
           return k





def insert(tree, node, key):
    tree[node]={'key':key,'P':None,'L':None,'R':None}
    y =None
    x = root(tree)
    node_key = tree[node]['key']
    while x is not None:
        y=x
        node_root=tree['R']['key']
        if node_key < node_root:
            x=tree[x]['L']
        else:
            x=tree[x]['R']
    tree[node]['P']=y
    if y is not None and node_key< tree[y]['key']:
        tree[y]['L']=node
    else:
        tree[y]['R']=node

    return  tree


def print_all(tree):
   for k,v in tree.items():
       print(k,v)
       print()
'''
Give a root node and key search target 
Returns the name of the node with associated key 
Else None
'''
def tree_search(tree,root, target):
    if root ==None:
        print(" key with node associate not found")
        return root
    if tree[root]['key'] == target:
        return  root
    if target < tree[root]['key']:
        return tree_search(tree,tree[root]['L'],target)
    else:
        return  tree_search(tree,tree[root]['R'],target)

def tree_iterative_search(tree,root,target):


    while root is not  None and tree[root]['key']!=target:

        if target < tree[root]['key']:
            root=tree[root]['L']


        else:
            root=tree[root]['R']


    return root

def minimum(tree,root):
    while tree[root]['L'] is not None:
        root=tree[root]['L']
    return tree[root]['key']






bst=add_root('R',20)

bst=insert(bst,'M',10)
bst=insert(bst,'B',8)
bst=insert(bst,'C',24)
bst=insert(bst,'D',22)
bst=insert(bst,'E',25)
bst=insert(bst,'G',25)
print_all(bst)
print(tree_search(bst,'R',25))
x=tree_iterative_search(bst,'R',25)
print(x)
#print(minimum(bst,'R'))
lucagiuseppe caliò
  • 1
  • 1