class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Sample Tree Structure:
#       1
#      / \
#     2   3
#    / \
#   4   5

# Building the tree:
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print("Tree constructed.")

def pre_order_traversal(node):
    if node:
        print(node.val, end=" ") # Visit Root
        pre_order_traversal(node.left) # Visit Left
        pre_order_traversal(node.right) # Visit Right

print("Pre-order Traversal:")
pre_order_traversal(root)
print()

def in_order_traversal(node):
    if node:
        in_order_traversal(node.left) # Visit Left
        print(node.val, end=" ") # Visit Root
        in_order_traversal(node.right) # Visit Right

print("In-order Traversal:")
in_order_traversal(root)
print()

def post_order_traversal(node):
    if node:
        post_order_traversal(node.left) # Visit Left
        post_order_traversal(node.right) # Visit Right
        print(node.val, end=" ") # Visit Root

print("Post-order Traversal:")
post_order_traversal(root)
print()

from collections import deque

def level_order_traversal(root_node):
    if not root_node:
        return

    queue = deque([root_node])
    
    while queue:
        node = queue.popleft()
        print(node.val, end=" ")

        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

print("Level-order Traversal:")
level_order_traversal(root)
print()

# Sample Graph Structure (undirected):
# 0 --- 1
# | \   |
# |  \  |
# 3 --- 2

graph = {
    0: [1, 2, 3],
    1: [0, 2],
    2: [0, 1, 3],
    3: [0, 2]
}

print("Graph adjacency list:")
for node, neighbors in graph.items():
    print(f"Node {node}: {neighbors}")

def dfs_recursive(graph, start_node, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start_node)
    print(start_node, end=" ")

    for neighbor in graph.get(start_node, []):
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

print("\nDFS (Recursive) Traversal starting from node 0:")
dfs_recursive(graph, 0)
print()

# Note: To ensure all components of a potentially disconnected graph are visited,
# you'd typically loop through all nodes and call DFS on unvisited ones.
# Example:
# all_nodes = set(graph.keys())
# visited_all = set()
# for node in all_nodes:
#     if node not in visited_all:
#         dfs_recursive(graph, node, visited_all) # Pass visited_all here

def dfs_iterative(graph, start_node):
    visited = set()
    stack = [start_node]
    
    while stack:
        node = stack.pop() # LIFO behavior for DFS
        
        if node not in visited:
            visited.add(node)
            print(node, end=" ")
            
            # Add unvisited neighbors to the stack.
            # Order might matter for specific path, but for full traversal it doesn't.
            # Reverse order ensures same output as recursive if neighbors sorted.
            for neighbor in sorted(graph.get(node, []), reverse=True): 
                if neighbor not in visited:
                    stack.append(neighbor)

print("\nDFS (Iterative) Traversal starting from node 0:")
dfs_iterative(graph, 0)
print()

from collections import deque

def bfs(graph, start_node):
    visited = set()
    queue = deque([start_node]) # FIFO behavior for BFS
    visited.add(start_node)
    
    while queue:
        node = queue.popleft()
        print(node, end=" ")
        
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

print("\nBFS Traversal starting from node 0:")
bfs(graph, 0)
print()

# Note: Similar to DFS, if the graph is disconnected,
# you'd iterate through all nodes and start BFS on unvisited ones
# to ensure full traversal of all components.

# Example for traversing all components
def traverse_all_components(graph, traversal_func):
    all_nodes = set(graph.keys())
    visited_overall = set()
    
    print(f"\nTraversing all components using {traversal_func.__name__}:")
    for node in sorted(all_nodes): # Sort for consistent output
        if node not in visited_overall:
            print(f"  Starting new traversal from {node}:", end=" ")
            # For this example, we'll redefine a version of the traversal functions
            # that takes and updates the overall visited set directly.
            # In a real scenario, the traversal_func would need a way to pass/update 'visited'.
            
            # Simple demonstration:
            if traversal_func.__name__ == "dfs_recursive":
                traversal_func(graph, node, visited_overall) # DFS recursive already handles visited internally if passed
            elif traversal_func.__name__ == "dfs_iterative_all": # A modified iterative DFS
                 stack = [node]
                 while stack:
                     current_node = stack.pop()
                     if current_node not in visited_overall:
                         visited_overall.add(current_node)
                         print(current_node, end=" ")
                         for neighbor in sorted(graph.get(current_node, []), reverse=True):
                             if neighbor not in visited_overall:
                                 stack.append(neighbor)
            elif traversal_func.__name__ == "bfs_all": # A modified BFS
                q = deque([node])
                visited_overall.add(node)
                while q:
                    current_node = q.popleft()
                    print(current_node, end=" ")
                    for neighbor in graph.get(current_node, []):
                        if neighbor not in visited_overall:
                            visited_overall.add(neighbor)
                            q.append(neighbor)
            else:
                print("Unknown traversal function.")
            print() # Newline after each component traversal

# Let's add an isolated node to our graph to simulate disconnectedness
graph_disconnected = {
    0: [1, 2],
    1: [0, 3],
    2: [0],
    3: [1],
    4: [] # Isolated node
}

# Define dummy functions for demonstration purposes of `traverse_all_components`
# In a real scenario, you'd modify dfs_recursive, dfs_iterative, bfs to accept/update a global visited set.
def dummy_dfs_recursive_wrapper(graph, start_node, visited):
    # This just ensures we print and update the global visited set for the example
    _internal_dfs(graph, start_node, visited)

def _internal_dfs(graph, node, visited):
    if node not in visited:
        visited.add(node)
        print(node, end=" ")
        for neighbor in graph.get(node, []):
            _internal_dfs(graph, neighbor, visited)

def dummy_dfs_iterative_all(graph, start_node, visited):
    # The actual logic is embedded in traverse_all_components due to how it uses `visited_overall`
    pass 

def dummy_bfs_all(graph, start_node, visited):
    # The actual logic is embedded in traverse_all_components due to how it uses `visited_overall`
    pass

# Demonstrate with the "modified" traversal functions
traverse_all_components(graph_disconnected, dummy_dfs_recursive_wrapper)
traverse_all_components(graph_disconnected, dummy_dfs_iterative_all)
traverse_all_components(graph_disconnected, dummy_bfs_all)

# Create a sample directory structure
mkdir -p my_project/src/main my_project/src/test my_project/docs
touch my_project/src/main/App.java my_project/src/main/Utils.java
touch my_project/src/test/AppTest.java
touch my_project/docs/README.md
touch my_project/README.md

echo "Directory structure created."

# Traverse and list all files and directories
echo "\nFiles and directories in my_project:"
find my_project -print

import os
import shutil

# Ensure the previous directory is cleaned up for a fresh run
if os.path.exists('my_project'):
    shutil.rmtree('my_project')

# Re-create the sample directory structure
os.makedirs('my_project/src/main')
os.makedirs('my_project/src/test')
os.makedirs('my_project/docs')
open('my_project/src/main/App.java', 'a').close()
open('my_project/src/main/Utils.java', 'a').close()
open('my_project/src/test/AppTest.java', 'a').close()
open('my_project/docs/README.md', 'a').close()
open('my_project/README.md', 'a').close()

print("Directory structure created for os.walk example.")

print("\nTraversing 'my_project' with os.walk:")
for dirpath, dirnames, filenames in os.walk('my_project'):
    print(f"Current Dir: {dirpath}")
    if dirnames:
        print(f"  Subdirectories: {dirnames}")
    if filenames:
        print(f"  Files: {filenames}")