Hauteur d'un arbre binaire

La hauteur d'un arbre, c'est comme compter le nombre d'etages d'un immeuble. C'est le nombre d'aretes (de liens) sur le chemin le plus long entre la racine et une feuille.

Conventions :
Un arbre vide (None) a une hauteur de -1
Un arbre avec seulement une racine a une hauteur de 0
Un arbre avec deux niveaux a une hauteur de 1

Pour un BST construit avec [5, 3, 7, 1], la hauteur est 2 (le chemin le plus long va de 5 a 3 puis a 1).

Écris une fonction hauteur(racine) qui retourne la hauteur de l'arbre.

Tests (2/4)

Arbre vide

assert hauteur(None) == -1

Racine seule

racine = insérer(None, 5)
assert hauteur(racine) == 0

+ 0 tests cachés

Indices (3 disponibles)

Solution officielle

class Node:
    def __init__(self, valeur):
        self.valeur = valeur
        self.gauche = None
        self.droite = None

def inserer(racine, valeur):
    if racine is None:
        return Node(valeur)
    if valeur < racine.valeur:
        racine.gauche = insérer(racine.gauche, valeur)
    else:
        racine.droite = insérer(racine.droite, valeur)
    return racine

def hauteur(racine):
    if racine is None:
        return -1
    return 1 + max(hauteur(racine.gauche), hauteur(racine.droite))

← Parcours d'arbre : inordre, preordre, … Compter les noeuds d'un arbre →

solution.py

Bravo!

Hauteur d'un arbre binaire

Tests (2/4)

Indices (3 disponibles)

Solution officielle