class TraeNode:
    def __init__(self, verdi):

        self._verdi = verdi
        self._lavere = None
        self._hoeyere = None

    def hentVerdi(self):
        return self._verdi

    def harLavereBarn(self):
        if self._lavere == None:
            return False
        return True

    def harHoeyereBarn(self):
        if self._hoeyere == None:
            return False
        return True

    def leggTilBarn(self, verdi):
        barn = TraeNode(verdi)

        if barn.hentVerdi() < self.hentVerdi():
            if not self.harLavereBarn():
                self._lavere = barn
            else:
                self._lavere.leggTilBarn(verdi)

        elif barn.hentVerdi() > self.hentVerdi():
            if not self.harHoeyereBarn():
                self._hoeyere = barn
            else:
                self._hoeyere.leggTilBarn(verdi)

    def skrivUtSortert(self):
        if self.harLavereBarn():
            self._lavere.skrivUtSortert()

        print(self._verdi)

        if self.harHoeyereBarn():
            self._hoeyere.skrivUtSortert()

    def hentSortertListe(self):
        liste = []
        if self.harLavereBarn():
            liste += self._lavere.hentSortertListe()
        liste.append(self._verdi)
        if self.harHoeyereBarn():
            liste += self._hoeyere.hentSortertListe()
        return liste