CODEWITHSUNDEEP
pythonrecursiontreebinary-tree
Pranav M
Pranav M

Reputation: 78

Recursion Working problem with dictionary

I have a doubt on recursion. Please help to clarify my doubt.

I have a data structure to store a Binary Tree node:

 class Node:
        def __init__(self, key, left=None, right=None):
            self.data = key
            self.left = left
            self.right = right
    # Recursive function to print left view of given binary tree
    def printLeftView(root,level=0,leveldic={}):
        if root==None:
            return
        print(root.data,leveldic)
        if level not in leveldic:
            leveldic[level]=root.data
            print(root.data)
        printLeftView(root.left,level+1,leveldic)
        printLeftView(root.right,level+1,leveldic)
    
"""
                      1
                    /    \
                   2       3
                  /      /    \
                4      5      6
                       \       
                        8

"""
if __name__ == '__main__':
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.right = Node(4)
    root.right.left = Node(5)
    root.right.right = Node(6)
    root.right.left.right = Node(8)
    printLeftView(root)

Output:

> ​1 {}
>     1
>     2 {0: 1}
>     2
>     4 {0: 1, 1: 2}
>     4
>     3 {0: 1, 1: 2, 2: 4}
>     5 {0: 1, 1: 2, 2: 4}
>     8 {0: 1, 1: 2, 2: 4}
>     8
>     6 {0: 1, 1: 2, 2: 4, 3: 8}

Doubt:

Why doesn't the dictionary go back to its orginal state after returning?

i.e., after print 4 dictionary is

{0: 1, 1: 2, 2: 4}

and since it return and when back to node 3, it should back to previous state while returning became

{0: 1, 1: 3}

this did not happen, the dictionary doesn't get the change and it is same as from the Node 4.

{0: 1, 1: 2, 2: 4}

What could be the reason?​

Upvotes: 0

Views: 421

Answers (2)

trincot
trincot

Reputation: 350242

The accepted answer is not correct: it will produce the wrong output.

The original code is exactly as the algorithm is supposed to work: there is one dictionary that is shared by all recursive execution contexts, and it should not return to a previous state when coming back from a recursive call. If you try to "fix" this, you will actually break the algorithm, and the output will generally be wrong then.

Be aware that the dictionary object is not deep-copied when you pass it as argument to a function: the function will get the argument in a new variable, but it is still the same dictionary. Unless a new value is assigned to that variable, any mutation to this dictionary will be to that single dictionary instance.

There is however another problem with your code: the default parameter value leveldic={} is problematic. This assignment happens only once, which is a behaviour that is quite specific to Python. This means that if you make the call again from the main program, you will still continue with the dictionary object as it was after the last call.

You would need it to get reset if such a second call is made:

def printLeftView(root, level=0, leveldic=None):
    if leveldic is None:
        leveldic = {}
    if root is None:
        return
    if level not in leveldic:
        leveldic[level] = root.data
        print(root.data)
    printLeftView(root.left, level + 1, leveldic)
    printLeftView(root.right, level + 1, leveldic)

Upvotes: 2

samor
samor

Reputation: 56

It seems that dictionary argument isn't a copy of dictionary, but reference to it in memory, so when it should back to node 3, it is with old keys. You must make copy of it.

def printLeftView(root,level=0,oldic={}):
    if root==None:
        return

    leveldic={} #making new dict
    for i in oldic:
        leveldic[i]=oldic[i] #and copying it values, to work on copy
    
    leveldic[level]=root.data
    print(root.data)
    print(root.data,leveldic)

    printLeftView(root.left,level+1,leveldic)
    printLeftView(root.right,level+1,leveldic)

Upvotes: 1

Related Questions