



from __future__ import annotations

from collections import defaultdict
from dataclasses import dataclass





@dataclass
class 		UpperCAmelCase    :
   SCREAMING_SNAKE_CASE__					      =  4_2
   SCREAMING_SNAKE_CASE__					      =  None
   SCREAMING_SNAKE_CASE__					      =  None






def 				UpperCAmelCase__		(					)->TreeNode:
      return TreeNode(3  ,					TreeNode(9					)  ,					TreeNode(2_0  ,					TreeNode(1_5					)  ,					TreeNode(7					)					)					)
def 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						Tuple					)->list[int]:

      def depth_first_search(
          _SCREAMING_SNAKE_CASE :						List[str]  ,					_SCREAMING_SNAKE_CASE :						Optional[Any]  ,					_SCREAMING_SNAKE_CASE :						Any					) -> None:
            if not root:
                  return

            if depth == len(_SCREAMING_SNAKE_CASE					):
                  right_view.append(root.val					)

            depth_first_search(root.right  ,					depth + 1  ,					_SCREAMING_SNAKE_CASE					)
            depth_first_search(root.left  ,					depth + 1  ,					_SCREAMING_SNAKE_CASE					)

      _lowerCAmelCase			      =	[]
      if not root:
            return right_view

      depth_first_search(_SCREAMING_SNAKE_CASE  ,					0  ,					_SCREAMING_SNAKE_CASE					)
      return right_view
def 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						Dict					)->list[int]:

      def depth_first_search(
          _SCREAMING_SNAKE_CASE :						Dict  ,					_SCREAMING_SNAKE_CASE :						Tuple  ,					_SCREAMING_SNAKE_CASE :						List[Any]					) -> None:
            if not root:
                  return

            if depth == len(_SCREAMING_SNAKE_CASE					):
                  left_view.append(root.val					)

            depth_first_search(root.left  ,					depth + 1  ,					_SCREAMING_SNAKE_CASE					)
            depth_first_search(root.right  ,					depth + 1  ,					_SCREAMING_SNAKE_CASE					)

      _lowerCAmelCase			      =	[]
      if not root:
            return left_view

      depth_first_search(_SCREAMING_SNAKE_CASE  ,					0  ,					_SCREAMING_SNAKE_CASE					)
      return left_view
def 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						Optional[Any]					)->list[int]:

      def breadth_first_search(_SCREAMING_SNAKE_CASE :						Dict  ,					_SCREAMING_SNAKE_CASE :						List[str]					) -> None:
            _lowerCAmelCase			      =	[(root, 0)]
            _lowerCAmelCase			      =	defaultdict(_SCREAMING_SNAKE_CASE					)

            while queue:
                  _lowerCAmelCase			      =	queue.pop(0					)
                  _lowerCAmelCase			      =	first

                  lookup[hd].append(node.val					)

                  if node.left:
                        queue.append((node.left, hd - 1)					)
                  if node.right:
                        queue.append((node.right, hd + 1)					)

            for pair in sorted(lookup.items()  ,					key=lambda _SCREAMING_SNAKE_CASE					: each[0]					):
                  top_view.append(pair[1][0]					)

      _lowerCAmelCase			      =	[]
      if not root:
            return top_view

      breadth_first_search(_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE					)
      return top_view
def 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						Optional[Any]					)->list[int]:
      from collections import defaultdict

      def breadth_first_search(_SCREAMING_SNAKE_CASE :						Dict  ,					_SCREAMING_SNAKE_CASE :						Optional[Any]					) -> None:
            _lowerCAmelCase			      =	[(root, 0)]
            _lowerCAmelCase			      =	defaultdict(_SCREAMING_SNAKE_CASE					)

            while queue:
                  _lowerCAmelCase			      =	queue.pop(0					)
                  _lowerCAmelCase			      =	first
                  lookup[hd].append(node.val					)

                  if node.left:
                        queue.append((node.left, hd - 1)					)
                  if node.right:
                        queue.append((node.right, hd + 1)					)

            for pair in sorted(lookup.items()  ,					key=lambda _SCREAMING_SNAKE_CASE					: each[0]					):
                  bottom_view.append(pair[1][-1]					)

      _lowerCAmelCase			      =	[]
      if not root:
            return bottom_view

      breadth_first_search(_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE					)
      return bottom_view


if __name__ == "__main__":
    import doctest

    doctest.testmod()

'''simple docstring'''







def 				_snake_case (		lowercase						)       ->       int:
				if not isinstance(lowercase			,    lowercase						):
								__a       :     Union[str, Any]								=	F"""Input value of [number={number}] must be an integer"""
								raise TypeError(lowercase						)
				if number < 1:
								raise ValueError("""Input must be a positive integer"""						)
				return number * (2 * number - 1)


if __name__ == "__main__":
					import doctest

					doctest.testmod()