Binary Tree BFS without queue

Question

I am working on a solution for https://leetcode.com/problems/binary-tree-level-order-traversal/submissions/.

I want to implement level order traversal without using a queue since that solution is quite trivial.

I have written the following code, which, in theory should work, but is giving the wrong result. I cant work out why.

Any help would be appreciated

class Node:
    # A utility function to create a new node
    def __init__(self, key):
        self.val = key
        self.left = None
        self.right = None
        
def height(root):
    if root is None:
        return 0
    else:
        heightL = height(root.left)
        heightR = height(root.right)
        maxHeight = max(heightL, heightR)
        return maxHeight + 1
        
def nodesOnLevel(root, level, result=[]):
    if root is None:
        return result
    if level == 1:
        result.append(root.val)
    elif level > 1:
        nodesOnLevel(root.left, level-1, result)
        nodesOnLevel(root.right, level-1, result)
    return result
   
    
def levelOrder_noQueue(root):
    if root is None:
        return
    levels = height(root)
    results = []
    for i in range(1, levels+1):
        results.append(nodesOnLevel(root, i))
    return results;

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print(levelOrder_noQueue(root))
# output is [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]]
# desired output is [[1], [2,3], [4,5]]

Answer 1

The problem is with result: there is only one result list in your code:

def nodesOnLevel(root, level, result=[]):

The default for result gets evaluated only once, when the script it parsed, not when the function is called. This means that when the levelOrder_noQueue function calls this function a second time (without passing a third argument), result will remain what it was, and the second call will just keep using it to append more elements.

So change this code to something like this:

def nodesOnLevel(root, level, result=None):
    if result is None:
        result = []

Or, otherwise, don't provide a default, and let the caller provide the empty list:

def nodesOnLevel(root, level, result):

And in levelOrder_noQueue:

    results.append(nodesOnLevel(root, i, []))