Wrote below solution to a leetcode problem https://leetcode.com/problems/binary-tree-inorder-traversal/-
# 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 inorderTraversal(self, root: Optional[TreeNode],traversal_list = []) -> List[int]:
if root:
traversal_list= self.inorderTraversal(root.left,traversal_list)
traversal_list.append(root.val)
traversal_list = self.inorderTraversal(root.right, traversal_list)
return traversal_list
Returns correct solution of [1,3,2] from example question #1. Returns [1,3,2] AGAIN from example question #2: [ ].
Why is answer #1 getting carried over to question #2?
CodePudding user response:
don't modify a parameter's default value
The template provided by LeetCode -
# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
The problem with your code is here -
- You added a third parameter,
traversal_list
, with a default value of[]
- In the non-recursive branch of the code, a reference to this list is returned
- In the recursive branch,
traversal_list
is mutated with.append
class Solution:
# ⚠️ 1
def inorderTraversal(self, root: Optional[TreeNode],traversal_list = []) -> List[int]:
if root:
traversal_list= self.inorderTraversal(root.left,traversal_list)
traversal_list.append(root.val) # ⚠️ 3
traversal_list = self.inorderTraversal(root.right, traversal_list)
return traversal_list # ⚠️ 2
recreation of the problem
This means subsequent calls to Solution#inorderTraversal
will contain a prepopulated traversal_list
and result in an incorrect answer. You can see a minimal recreation of the problem in below -
def foo (x = []):
x.append(1)
return x
print(foo()) # [1]
print(foo()) # [1, 1] # ❌
In another example, look how the default parameter value is evaluated only once when the script is executed -
def hello():
print(1)
return 3
def foo (x = hello()): # ⚠️ hello() happens first
return x
print(2) # ⚠️ this is actually second!
print(foo())
1
2
3
fix it
To fix it, remove the third parameter, traversal_list
. There's no need for it. Simply return []
when root
is not present -
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if root:
left = self.inorderTraversal(root.left)
right = self.inorderTraversal(root.right)
return left [root.val] right
else:
return []
An improved way to write this is to write a traversal function outside of the class -
def inorder(t):
if t:
yield from inorder(t.left)
yield t.val
yield from inorder(t.right)
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
return list(inorder(root))
"what if i want to use append?"
If you want to use a single output
list and .append
, there is another option available to you -
def inorder(root):
output = []
def traverse(t):
if t:
traverse(t.left)
output.append(t.val)
traverse(t.right)
traverse(root)
return output
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
return inorder(root)
not a universal behavior
Note this behaviour is in direct contrast to other languages. For example, JavaScript will re-evaluate a parameter's default value each time the function is run -
function foo(x = []) {
x.push(1)
return x
}
console.log(foo()) // [1]
console.log(foo()) // [1]