Path to each Leaf of a Binary Tree

Solution 1:

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]]

Solution 2:

One method is to do it by backtracking:

def allPaths(node, partial_res, res):
    if not node: 
        return
    if not node.left and not node.right:
        res.append(partial_res[:] + [node.value])
        return    
    partial_res.append(node.value)
    allPaths(node.left, partial_res, res)
    allPaths(node.right, partial_res, res)
    partial_res.pop()

res = []
allPaths(root, [], res)
print(res)

Solution 3:

I offer another option.

def allPaths(root, path=[]):
    tmp = []
    if root.left:
        tmp.extend(allPaths(root.left, path + [root.value]))
    if root.right:
        tmp.extend(allPaths(root.right, path + [root.value]))
    if not root.left and not root.right:
        tmp.append(path + [root.value])
    return tmp


tree = allPaths(root)
print(tree)

The output is:

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