CODEWITHSUNDEEP
pythonrecursiondata-structurestree
Ayush Tripathi
Ayush Tripathi

Reputation: 11

Recursion operation in Pre-order tree traversal

Pre-order traversal is simple recursive procedure. I am perplexed with two implementations behaving differently.

Input passed to both implementations are:

[1,null,2,3]
[]
[1]

Expected output for above input-

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

1st implementation-

class Solution:
    ans=[]
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return
        self.ans.append(root.val)
        self.preorderTraversal(root.left)
        self.preorderTraversal(root.right)
        
        return self.ans

Output-

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

2nd implementation-

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        self.ans=[]
        def preorder(root):
            if root is None:
                return
            self.ans.append(root.val)
            preorder(root.left)
            preorder(root.right)
        preorder(root)
        return self.ans

This gives correct output

What is wrong with the 1st implementation?

Upvotes: 0

Views: 111

Answers (1)

user2976612
user2976612

Reputation: 137

In 1st implementation you define class field ans shared between class instances. Thus when you run the code for last example ans has value [1, 2, 3].

In 2nd implementation you define instance field. In this case ans belong to instance, not class.

Upvotes: 1

Related Questions