Chapter 08: Trees

class TreeNode:
    """Each node is an object with references to its children."""
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left    # Pointer to left child (or None)
        self.right = right  # Pointer to right child (or None)

# Building a tree:
#        1
#       / \
#      2   3
#     / \
#    4   5

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# A binary tree can be stored in a flat array using level-order (BFS order).
# The index arithmetic lets you find parent and children in O(1):
#
#   Parent of node at index i:      (i - 1) // 2
#   Left child of node at index i:  2 * i + 1
#   Right child of node at index i: 2 * i + 2
#
# Tree:       1
#            / \
#           2   3
#          / \
#         4   5
#
# Array: [1, 2, 3, 4, 5]
# Index:  0  1  2  3  4
#
# For incomplete trees, we use None for missing nodes:
# Tree:       1
#            / \
#           2   3
#            \
#             5
# Array: [1, 2, 3, None, 5]

tree_array = [1, 2, 3, 4, 5]

def get_left_child_index(i):
    return 2 * i + 1

def get_right_child_index(i):
    return 2 * i + 2

def get_parent_index(i):
    return (i - 1) // 2

# Access children of node at index 0 (value 1):
left_idx = get_left_child_index(0)   # 1 → value 2
right_idx = get_right_child_index(0)  # 2 → value 3

from collections import deque

def array_to_tree(arr: list) -> 'TreeNode | None':
    """
    Convert level-order array [1, 2, 3, None, 5] to node objects.

    This is how LeetCode inputs are typically given — you'll need this
    to test your solutions locally.

    Time: O(n) — process each element once
    Space: O(n) — create n nodes
    """
    if not arr or arr[0] is None:
        return None

    root = TreeNode(arr[0])
    queue = deque([root])  # BFS queue to assign children level by level
    i = 1  # Index into the array

    while queue and i < len(arr):
        node = queue.popleft()  # O(1       )

        # Assign left child
        if i < len(arr) and arr[i] is not None:
            node.left = TreeNode(arr[i])
            queue.append(node.left)
        i += 1

        # Assign right child
        if i < len(arr) and arr[i] is not None:
            node.right = TreeNode(arr[i])
            queue.append(node.right)
        i += 1

    return root


def tree_to_array(root: 'TreeNode | None') -> list:
    """
    Convert node objects back to level-order array.

    Time: O(n) — visit each node once (BFS)
    Space: O(n) — the output array + BFS queue
    """
    if root is None:
        return []

    result = []
    queue = deque([root])

    while queue:
        node = queue.popleft()  # O(1)
        if node:
            result.append(node.value)
            queue.append(node.left)   # May be None
            queue.append(node.right)  # May be None
        else:
            result.append(None)

    # Remove trailing Nones (they're just padding)
    while result and result[-1] is None:
        result.pop()

    return result