class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []  # List of child nodes

# Recursive DFS Function
def dfs_recursive(node):
    if node is None:
        return
    print(node.value, end=" ")  # Process the current node
    for child in node.children:
        dfs_recursive(child)

# Iterative DFS Function
def dfs_iterative(node):
    if node is None:
        return
    stack = [node]  # Initialize stack with the root node
    while stack:
        current = stack.pop()
        print(current.value, end=" ")  # Process the current node
        # Add children to the stack in reverse order (rightmost child first)
        stack.extend(reversed(current.children))

# Build the tree as per the image
root = TreeNode(1)
child2 = TreeNode(2)
child7 = TreeNode(7)
child8 = TreeNode(8)

child2.children = [TreeNode(3), TreeNode(6)]
child2.children[0].children = [TreeNode(4), TreeNode(5)]

child7.children = [TreeNode(9)]
child7.children[0].children = [TreeNode(10)]

child8.children = [TreeNode(12), TreeNode(11)]

root.children = [child2, child7, child8]

# Run DFS
print("Recursive DFS Traversal:")
dfs_recursive(root)

print("\nIterative DFS Traversal:")
dfs_iterative(root)