Tried out the Binary Tree Inorder Traversal using recursive. Where am I going wrong?

Question

Test cases passes individually, but when submitted, the first Output just stays in the list.

Cant wrap my head around it. What is happening?

class Solution:

l=[]

def inorderTraversal(self, root: TreeNode) -> List[int]:

    if root is None:
        return self.l
    else:
        if root.left:
            self.inorderTraversal(root.left)
        self.l.append(root.val)
        if root.right:
            self.inorderTraversal(root.right)

        return self.l

***Test Case***

> Your input [1] 
Output [1] 

Expected [1]

**Submitted**

> Wrong Answer Details 
Input [] 
Output [1,3,2] 
Expected []

Sylvaus · Answer 1 · 2020-05-24T15:02:36.733

I think the problem is that you do not initialize l in a constructor __init__(self)
By declaring l the way you did, it will be shared by all the instance of Solution. This most probably your problem since the testing code probably instantiates a new Solution for every case.

Your could add the following to your solution class to ensure that l is not shared by the Solution instances:

class Solution:
    def __init__(self):
        self.l=[]

If it still does not work, the class solution is probably instantiated once and the method inorderTraversal is probably called on each test inputs

In this case you have to slightly to change you inorderTraversal:

def inorderTraversal(self, root: TreeNode) -> List[int]:
    result = []
    if root is None:
        return result
    else:
        if root.left:
            result.extend(self.inorderTraversal(root.left))
        result.append(root.val)
        if root.right:
            result.extend(self.inorderTraversal(root.right))

        return result

and you can simplify the code to:

def inorderTraversal(self, root: TreeNode) -> List[int]:
    result = []
    if root.left:
        result.extend(self.inorderTraversal(root.left))
    result.append(root.val)
    if root.right:
        result.extend(self.inorderTraversal(root.right))

     return result

Tried out the Binary Tree Inorder Traversal using recursive. Where am I going wrong?

1 Answers1