structy | all tree paths iterative

all-tree-paths.py

class Node:
    def __init__(self, val):
        self.val = val
        self.left: Node | None = None
        self.right: Node | None = None


def all_tree_paths(root: "Node") -> list[str]:
    result = []
    stack = [(root, [root.val])]

    while stack:
        curr, path = stack.pop()

        if not curr.left and not curr.right:
            result.append(path[:])
            continue

        if curr.right:
            stack.append((curr.right, path + [curr.right.val]))
        if curr.left:
            stack.append((curr.left, path + [curr.left.val]))

    return result


a = Node("a")
b = Node("b")
c = Node("c")
d = Node("d")
e = Node("e")
f = Node("f")

a.left = b
a.right = c
b.left = d
b.right = e
c.right = f

#      a
#    /   \
#   b     c
#  / \     \
# d   e     f

all_tree_paths(a)  # ->
# [
#   [ 'a', 'b', 'd' ],
#   [ 'a', 'b', 'e' ],
#   [ 'a', 'c', 'f' ]
# ]