





'''simple docstring'''






from __future__ import annotations

from collections.abc import Iterable, Iterator
from dataclasses import dataclass

A__							:  str    =(3, 9, -11, 0, 7, 5, 1, -1)
A__							:  Union[str, Any]    =(4, 6, 2, 0, 8, 10, 3, -2)




@dataclass
class 					UpperCAmelCase	:
      _lowercase:     int
      _lowercase:     Node | None




class 					UpperCAmelCase	:




      def __init__(     self     :					Tuple     ,     __snake_case     :					Iterable[int]    )							-> None:
            _lowerCAmelCase					=				None
            for i in sorted(__snake_case     ,     reverse=__snake_case    ):
                  _lowerCAmelCase					=				Node(__snake_case     ,     self.head    )




      def __iter__(     self     :					Tuple    )							-> Iterator[int]:
            _lowerCAmelCase					=				self.head
            while node:
                  yield node.data
                  _lowerCAmelCase					=				node.next_node




      def __len__(     self     :					List[str]    )							-> int:
            return sum(1 for _ in self    )




      def __str__(     self     :					List[str]    )							-> str:
            return " -> ".join([str(__snake_case    ) for node in self]    )




def   UpperCamelCase__ (						lowerCAmelCase				,      lowerCAmelCase    ):





      """simple docstring"""


      return SortedLinkedList(list(lowerCAmelCase    ) + list(lowerCAmelCase    )    )


if __name__ == "__main__":
      import doctest

      doctest.testmod()
      A__							:  Optional[Any]    =SortedLinkedList
      print(merge_lists(SSL(test_data_odd), SSL(test_data_even)))













'''simple docstring'''






class 					UpperCAmelCase	:




      def __init__(     self     :					List[str]     ,     __snake_case     :					str    )							-> Union[str, Any]:
            _lowerCAmelCase					=				val
            _lowerCAmelCase					=				None
            _lowerCAmelCase					=				None




      def 							lowercase__       (     self     :					Optional[Any]     ,     __snake_case     :					int    )							-> Optional[int]:
            if self.val:
                  if val < self.val:
                        if self.left is None:
                              _lowerCAmelCase					=				Node(__snake_case    )
                        else:
                              self.left.insert(__snake_case    )
                  elif val > self.val:
                        if self.right is None:
                              _lowerCAmelCase					=				Node(__snake_case    )
                        else:
                              self.right.insert(__snake_case    )
            else:
                  _lowerCAmelCase					=				val




def   UpperCamelCase__ (						lowerCAmelCase				,      lowerCAmelCase    ):





      """simple docstring"""


      if root:
            inorder(root.left				,      lowerCAmelCase    )
            res.append(root.val    )
            inorder(root.right				,      lowerCAmelCase    )
def   UpperCamelCase__ (						lowerCAmelCase    ):





      """simple docstring"""


      if len(lowerCAmelCase    ) == 0:
            return arr
      _lowerCAmelCase					=				Node(arr[0]    )
      for i in range(1				,      len(lowerCAmelCase    )    ):
            root.insert(arr[i]    )
      # Traverse BST in order.
      _lowerCAmelCase					=				[]
      inorder(lowerCAmelCase				,      lowerCAmelCase    )
      return res


if __name__ == "__main__":
      print(tree_sort([10, 1, 3, 2, 9, 14, 13]))






