Binary Tree Inorder Traversal - Recursive

Question

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?

Answer 1

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 -

1. You added a third parameter, traversal_list, with a default value of []
2. In the non-recursive branch of the code, a reference to this list is returned
3. 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 absolutely want to use .append, you can model the solution above in a similar way.

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] ? differs from python's behaviour

function hello() {
  console.log(1)
  return 3
}

function foo(x = hello()) {
  return x
}

console.log(2)
console.log(foo())

2
1  // ? differs from python's behaviour
3

Answer 2

class Solution:

def inorderTraversal(self, root: Optional[TreeNode],traversal_list = []) -> List[int]:
    print(root)
    print('\n')
    if not root:
        return []
    print(root.left)
    if root.left:
        yield from self.inorderTraversal(root.left)
    yield root.val
    print(root.right)
    if root.right:
        yield from self.inorderTraversal(root.right)