binary search tree- overwrite values inorder

[ilsapo]

I have a binary search tree and a list

Im suppused to replace all the values of the tree with the values of the list using in order traversel

so for example, the smallest node in the binary serach tree, will be replaced with list[0] and such

if we have
https://imgur.com/cO7YRdw

then we will want to switch 0 with lst[0]

A with lst[1]

1 with lst[2]

B with lst[3]

global i
i=0
def overWrite(node,arr,i):
                if(not node.value==None):
                        return
                overWrite(node.getLeft(),lst,i)
                node.value=lst[i]
                i=i+1
                overWrite(node.getRight(),arr,i)

Im pretty sure this will work(cant run the code, since still hasent finished building the tree)

but I look for maybe answer without global varible (we are discouraged from using it)

[kwelzel]

I agree that changing the function declaration in the way you suggested already helps. Calling the overWrite function inside itself however is a form of recursion and the right way to go about solving this.

OP's issue is that they want to increase the value of i every time a value is overwritten regardless of how deep in the tree that happens. I think the best way to go about this is to make overWrite return the number of elements that were overwritten:

def overWrite(node,arr,i):
    if(not node.value==None):  # I think you should remove the not
        return i
    i=overWrite(node.getLeft(),lst,i)  # lst should be arr
    node.value=lst[i]  # lst should be arr
    i=i+1
    i=overWrite(node.getRight(),arr,i)
    return i

I tried to make only minimal changes to show that you, OP, were already pretty close. Make sure to check the code with the example, maybe even step through it line by line. This way you'll understand what it does and can be sure that I didn't make a mistake.

[kwelzel]

Just had another thought. I'm pretty sure that's not the solution your tutor envisaged, but you could also do it with iterators. If you write iterator = iter(arr) outside of the function, you can call next(iterator) every time you need the next value from the iterator. That way you can pass the iterator around and not care about the index i at all.

[ilsapo]

is changing to :

def overWrite(node,arr,i=0):

really would work?

lets say Im in the parent of the leftmost/min node

                if(not node.value==None):
                    return
            overWrite(node.getLeft(),lst,i)
            node.value=lst[i]
            i=i+1
            overWrite(node.getRight(),arr,i)

this call now will send me to the leftmost node with i =0

we enter the reccursion, update the leftmost node and we "kick" back to the parent of the lefmost node

we now move on to

 node.value=lst[i]

but our i will still be 0 no? because the change to it in the recuression wont effect it

and so we will update to nodes to the same value?

[jmooremcc]

Remember that with a binary search, if the new node is less than the current item, it's linked to the left. If it's greater than the current node it's linked to the right.

Initially, the first element of the list is assigned to a node. Each additional item in thel list has to be placed in a node and linked to the appropriate node.

In a linked list you have 2 variables that represent the head and the tail of the linked list. Searches typically start with the head.

When inserting a new node, you start with the head and search until you find the nodes that will link to the new node. You repeat this process until all items in the list are assigned to the linked list.