




'''simple docstring'''



from __future__ import annotations

from collections import defaultdict
from dataclasses import dataclass





@dataclass
class       lowerCAmelCase				:
       __lowercase					: int
       __lowercase					: TreeNode | None	    =     None
       __lowercase					: TreeNode | None	    =     None







def      _UpperCamelCase	()->				TreeNode:




     '''simple docstring'''





     return TreeNode(3				,		TreeNode(9		)				,		TreeNode(20				,		TreeNode(15		)				,		TreeNode(7		)		)		)







def      _UpperCamelCase	(_lowerCamelCase							:       TreeNode		)->				list[int]:




     '''simple docstring'''





     def depth_first_search(
         _lowerCamelCase							:       TreeNode | None				,		_lowerCamelCase							:       int				,		_lowerCamelCase							:       list[int]		) -> None:
          if not root:
               return

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

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

     __snake_case         =					[]
     if not root:
          return right_view

     depth_first_search(_lowerCamelCase				,		0				,		_lowerCamelCase		)
     return right_view







def      _UpperCamelCase	(_lowerCamelCase							:       TreeNode		)->				list[int]:




     '''simple docstring'''





     def depth_first_search(
         _lowerCamelCase							:       TreeNode | None				,		_lowerCamelCase							:       int				,		_lowerCamelCase							:       list[int]		) -> None:
          if not root:
               return

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

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

     __snake_case         =					[]
     if not root:
          return left_view

     depth_first_search(_lowerCamelCase				,		0				,		_lowerCamelCase		)
     return left_view







def      _UpperCamelCase	(_lowerCamelCase							:       TreeNode		)->				list[int]:




     '''simple docstring'''





     def breadth_first_search(_lowerCamelCase							:       TreeNode				,		_lowerCamelCase							:       list[int]		) -> None:
          __snake_case         =					[(root, 0)]
          __snake_case         =					defaultdict(_lowerCamelCase		)

          while queue:
               __snake_case         =					queue.pop(0		)
               __snake_case   ,      __snake_case         =					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 _lowerCamelCase		: each[0]		):
               top_view.append(pair[1][0]		)

     __snake_case         =					[]
     if not root:
          return top_view

     breadth_first_search(_lowerCamelCase				,		_lowerCamelCase		)
     return top_view







def      _UpperCamelCase	(_lowerCamelCase							:       TreeNode		)->				list[int]:




     '''simple docstring'''





     from collections import defaultdict

     def breadth_first_search(_lowerCamelCase							:       TreeNode				,		_lowerCamelCase							:       list[int]		) -> None:
          __snake_case         =					[(root, 0)]
          __snake_case         =					defaultdict(_lowerCamelCase		)

          while queue:
               __snake_case         =					queue.pop(0		)
               __snake_case   ,      __snake_case         =					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 _lowerCamelCase		: each[0]		):
               bottom_view.append(pair[1][-1]		)

     __snake_case         =					[]
     if not root:
          return bottom_view

     breadth_first_search(_lowerCamelCase				,		_lowerCamelCase		)
     return bottom_view


if __name__ == "__main__":
     import doctest

     doctest.testmod()












'''simple docstring'''



def      _UpperCamelCase	(_lowerCamelCase							:       list				,		_lowerCamelCase							:       int		)->				int:




     '''simple docstring'''





     for index, item in enumerate(_lowerCamelCase		):
          if item == target:
               return index
     return -1







def      _UpperCamelCase	(_lowerCamelCase							:       list				,		_lowerCamelCase							:       int				,		_lowerCamelCase							:       int				,		_lowerCamelCase							:       int		)->				int:




     '''simple docstring'''





     if not (0 <= high < len(_lowerCamelCase		) and 0 <= low < len(_lowerCamelCase		)):
          raise Exception('''Invalid upper or lower bound!'''		)
     if high < low:
          return -1
     if sequence[low] == target:
          return low
     if sequence[high] == target:
          return high
     return rec_linear_search(_lowerCamelCase				,		low + 1				,		high - 1				,		_lowerCamelCase		)


if __name__ == "__main__":
     UpperCAmelCase_    :					List[Any]					      =						input('''Enter numbers separated by comma:\n''').strip()
     UpperCAmelCase_    :					Optional[int]					      =						[int(item.strip()) for item in user_input.split(''',''')]

     UpperCAmelCase_    :					List[str]					      =						int(input('''Enter a single number to be found in the list:\n''').strip())
     UpperCAmelCase_    :					Optional[int]					      =						linear_search(sequence, target)
     if result != -1:
          print(F"""linear_search({sequence}, {target}) = {result}""")
     else:
          print(F"""{target} was not found in {sequence}""")






