CODEWITHSUNDEEP
python-2.7treebinary-search-tree
codefreak
codefreak

Reputation: 309

Replace node values with their depths in a tree in python

i need to fill up this visitor class so it can be used to fill nodes with depth in a single pass
Example:
Consider the tree as

                 12
                /  \
               30  50
              / \   /
             40 50 60
                   /
                  70

If i consider a tree whose preorder traversal is given as 

[12,30,40,50,50,60,70]

the o/p(preorder traversal) i should get is

[0,1,2,2,1,2,3]

that means the actual node values have to be replaced by their corresponding depths


The visitor function i wrote is as 

class DepthVisitor(object):
    def __init__(self):
        self.result=[]
        pass
    def fill_depth(self, node):
        def count(node, level):
            if node!=None:
                node.value=level
                level+=1
                count(node.left, level)
                if node.left==None:
                    count(node.right,level)
        count(node, 0)
        pass

visitor = DepthVisitor()
pre_order(root, visitor.fill_depth)

the problem is that every time the node is passed to the visitor function it's value gets overwritten to 0 and hence the o/p comes as

[0,0,0,0,0,0,0]

How can i prevent it from overwriting the already visited node values to 0 so as to get the correct o/p.
Or is there any alternate/better way to the same w/o using recursion??

Upvotes: 0

Views: 1126

Answers (1)

Nat Dempkowski
Nat Dempkowski

Reputation: 2440

You should initialize your DepthVisitor to have a level attribute by doing self.level = 0. You can then modify your count function to use that persistent level, as it will be stored in the object scope instead of the function scope. You can increment and decrement it as appropriate across function calls.

Upvotes: 1

Related Questions