Rewriting recursive python function without helper causes it to stop working

Question

Basically a tried to rewrite a recursive function in Python without using a helper function. The code is almost identical, but I'm getting lots of unexpected results. Can anyone tell what I'm missing?

Here is the working code:

class BST:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def reconstructBst(preOrderTraversalValues):
    root_index = [0]
    return reconstructFromRange(float("-inf"), float("inf"), preOrderTraversalValues, root_index)
    
def reconstructFromRange(low, high, values, root_index):
    if root_index[0] == len(values):
        return None
    
    root_value = values[root_index[0]]
    if root_value < low or root_value >= high:
        return None
    
    root_index[0] += 1
    left_subtree = reconstructFromRange(low, root_value, values, root_index)
    right_subtree = reconstructFromRange(root_value, high, values, root_index)
    return BST(root_value, left_subtree, right_subtree)

Here is the non-working rewrite:

class BST:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def reconstructBst(preOrderTraversalValues, low=float("-inf"), high=float("inf"), root_index=[0]):

    if root_index[0] == len(preOrderTraversalValues):
        return None
    
    root_value = preOrderTraversalValues[root_index[0]]
    if root_value < low or root_value >= high:
        return None
    
    root_index[0] += 1
    left_subtree = reconstructBst(preOrderTraversalValues, low, root_value, root_index)
    right_subtree = reconstructBst(preOrderTraversalValues, root_value, high, root_index)
    return BST(root_value, left_subtree, right_subtree)

Here is the error that comes up for most of the test cases:

 list index out of range
 Traceback (most recent call last):
  File "/tester/json_wrapper.py", line 30, in getActual
    result = program.reconstructBst(preOrderTraversalValues)
  File "/tester/program.py", line 13, in reconstructBst
    root_value = preOrderTraversalValues[root_index[0]]
IndexError: list index out of range

Answer 1

In the original code, whenever reconstructBst runs, it creates a new root_index = [0] and gives it to reconstructFromRange, which mutates root_index in the line root_index[0] += 1.

In your edit, you moved the creation root_index=[0] to a default argument of reconstructBst. It is not created when reconstructBst runs, but at its DEFINITION; think of it as an object that belongs to the function itself. Now every time reconstructBst runs, it changes its root_index value.

I'll bet that root_index was no longer [0] after the first run, and that caused a problem because preOrderTraversalValues only starts with 1 value and could only be indexed by preOrderTraversalValues[0].

The easy fix is to use a dummy immutable value to specify when to create a mutable object:

def reconstructBst(preOrderTraversalValues, low=float("-inf"), high=float("inf"), root_index=None):
     if root_index == None:
         root_index = [0]    
     ...