from __future__ import annotations
from typing import Any, Optional


class Tree:
    """A recursive tree data structure.

    Representation Invariants:
        - self._root is not None or self._subtrees == []
    """
    # Private Instance Attributes:
    #   - _root:
    #       The item stored at this tree's root, or None if the tree is empty.
    #   - _subtrees:
    #       The list of subtrees of this tree. This attribute is empty when
    #       self._root is None (representing an empty tree). However, this attribute
    #       may be empty when self._root is not None, which represents a tree consisting
    #       of just one item.
    _root: Optional[Any]
    _subtrees: list[Tree]

    def __init__(self, root: Optional[Any], subtrees: list[Tree]) -> None:
        """Initialize a new Tree with the given root value and subtrees.

        If root is None, the tree is empty.

        Preconditions:
            - root is not none or subtrees == []
        """
        self._root = root
        self._subtrees = subtrees

    def is_empty(self) -> bool:
        """Return whether this tree is empty.
        """
        return self._root is None

    def first_at_depth(self, d: int) -> Optional[Any]:
        """Return the leftmost value at depth d in this tree.

        Return None if there are NO items at depth d in this tree.

        Preconditions:
            - d >= 0
        """
        if self.is_empty():
            return None
        elif self._subtrees == []:
            if d == 0:
                return self._root
            else:
                return None
        else:
            if d == 0:
                return self._root
            for subtree in self._subtrees:
                rec_value = subtree.first_at_depth(d - 1)
                if rec_value is not None:
                    return rec_value
            return None

    # def __str__(self) -> str:
    def _str_helper(self, depth) -> str:
        if self.is_empty():
            return ''
        else:
            indentation = depth * ' '
            str_so_far = indentation + f'{self._root}\n'
            for subtree in self._subtrees:
                str_so_far += subtree._str_helper(depth + 1)
            return str_so_far