[FIXED] Path to each Leaf of a Binary Tree

Issue

The function above AllPaths() append an array containing the path to each leaf of the binary tree to the global array res.

The code works just fine, but I want to remove the global variable res and make the function return an array instead. How can I do that?

class Node:
    def __init__(self, value, left=None, right=None) -> None:
        self.value = value
        self.left  = left
        self.right = right

res = []
def allPaths(node, arr=[]):
    if node:
        tmp = [*arr, node.value]
        if not node.left and not node.right: # Leaf
            res.append(tmp)
        allPaths(node.left, tmp)
        allPaths(node.right, tmp)


root             = Node(1)
root.left        = Node(2);
root.left.left   = Node(4);
root.left.right  = Node(5);
root.right       = Node(3);
root.right.right = Node(6);
"""
          1         <-- root
        /   \
       2     3  
     /   \    \
    4     5    6    <-- leaves
"""
allPaths(root)
print(res)
# Output : [[1, 2, 4], [1, 2, 5], [1, 3, 6]]

Solution

A simple way that allow you to avoid the inner lists and global list altogether is to make a generator that yields the values as they come. Then you can just pass this to list to make the final outcome:

class Node:
    def __init__(self, value, left=None, right=None) -> None:
        self.value = value
        self.left  = left
        self.right = right

def allPaths(node):  
    if node:
        if not node.left and not node.right: # Leaf
            yield [node.value]
        else:
            yield from ([node.value] + arr for arr in allPaths(node.left))
            yield from ([node.value] + arr for arr in allPaths(node.right))
              
root             = Node(1)
root.left        = Node(2);
root.left.left   = Node(4);
root.left.right  = Node(5);
root.right       = Node(3);
root.right.right = Node(6);
        
g = allPaths(root)
list(g)

# [[1, 2, 4], [1, 2, 5], [1, 3, 6]]

Answered By - Mark