Leetcode "Binary Tree Preorder Traversal" issue

Question

I'm trying to solve trivial binary tree preorder traversal problem from LeetCode. Here is my solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
     def preorderTraversal(self, root: TreeNode, node_list = []) -> List[int]:
        if not root:
            return []
        
        node_list.append(root.val)
        for leaf in (root.left, root.right):
            if leaf is not None:
                self.preorderTraversal(leaf, node_list)
        return node_list

but it don't pass following testcase:

Input: [1]
Output: [1,2,3,1]
Expected: [1]

How can it be possible to get output [1,2,3,1] from one single node which has no leafs at all. For me, it should add value of the first node (1) to the values list, iteratively check children-nodes (both of them should be None) and return node-values list, (which consist of the only not-None value from the first node - [1]). From where it gets 2,3,1 values if the tree consists form one single node: val = 1, left = None, right = None?
I am definitely missing something obvious, but cannot figure out what exactly. Please help me out.

Your problem is the `node_list = []`. Every call to `preorderTraversal` is going to be using the exact same list. The `[1, 2, 3]` is probably left over from the previous call to this method. This is a well-known gotcha in Python, and one of the reasons you must never default initialize a variable to a list. https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument — Frank Yellin, Nov 14 '21 at 01:17
I would suggest that you change your code to use a helper method that does nothing bug appends items to a list passed to it as an argument. It will be recursive. Then `preorderTraversal(node)` does `lst = []; helper(node, lst); return lst` — Frank Yellin, Nov 14 '21 at 01:20
@FrankYellin thank you. It's not the first time I got caught on default argument initialization. I just didn't think of it, because I was looking towards the algorithm, not of the language peculiarities . — Kaderma, Nov 14 '21 at 01:39

score 0 · Answer 1 · answered Nov 14 '21 at 01:24

As Frank Yellin noted in the comments the problem is with the default list to the function.

Here's a version that works:

class Solution:

    def preorderTraversal(self, root: TreeNode) -> List[int]:
        return self.helper(root, [])
            
    def helper(self, node, node_list): 
        if not node:
            return []
        
        node_list.append(node.val)
        for leaf in (node.left, node.right):
            if leaf is not None:
                self.helper(leaf, node_list)
        return node_list

The code is all yours. I just created a helper function with the meat of the algorithm taken out of the main function.

Leetcode "Binary Tree Preorder Traversal" issue

1 Answers1