Inverser un Arbre Binaire en Python : Question Fréquente des Entretiens de Codage

Introduction

Les arbres binaires sont l’un des fondements de la programmation informatique, en particulier dans le domaine des structures de données. Ils sont fréquemment utilisés pour représenter des hiérarchies et effectuer des recherches efficaces. Dans cet article, nous allons explorer le problème largement discuté de l’inversion d’un arbre binaire, une question populaire lors des entretiens techniques en raison de sa capacité à tester la compréhension fondamentale des candidats de la récursivité, des structures de données et de la manipulation d’arbres.

Comprendre les Arbres Binaires

Qu’est-ce qu’un Arbre Binaire ?

Un arbre binaire est une structure de données non linéaire composée de nœuds, où chaque nœud a au plus deux enfants : un enfant gauche et un enfant droit. Un arbre binaire est constitué de plusieurs composants :

• Nœud : élément qui contient une valeur, ainsi que des références vers ses enfants gauche et droit.
• Racine : le nœud de départ de l’arbre, le sommet de la structure.
• Feuilles : nœuds qui n’ont pas d’enfants.
• Sous-arbre : une section de l’arbre constituée d’un nœud et de ses descendants.

Types d’Arbres Binaires

• Arbre Binaire Complet : chaque niveau de l’arbre est entièrement rempli, sauf peut-être le dernier, qui est rempli de gauche à droite.
• Arbre Binaire Parfait : tous les niveaux de l’arbre sont complètement remplis.
• Arbre Binaire Équilibré : la hauteur de l’arbre est minimale pour le nombre de nœuds.
• Arbre Binaire de Recherche : pour chaque nœud, les valeurs du sous-arbre gauche sont inférieures à la valeur du nœud, et celles du sous-arbre droit sont supérieures.

Concept d’Inversion d’un Arbre Binaire

Inverser un arbre binaire consiste à échanger les enfants gauche et droit de chaque nœud de l’arbre. Voici une illustration simple :

Avant inversion :

    1
   / \
  2   3
 / \
4   5

Après inversion :

    1
   / \
  3   2
     / \
    5   4

Stratégies pour Inverser un Arbre Binaire

Approche Récursive

L’approche récursive est intuitive pour traverser et inverser les arbres. Le concept repose sur l’appel de la même fonction pour les nœuds enfants jusqu’à atteindre une feuille. Voici un pseudocode pour illustrer cela :

function invertTree(node):
    if node is null:
        return null
    swap(node.left, node.right)
    invertTree(node.left)
    invertTree(node.right)
    return node

Approche Itérative

Une inversion itérative utilise souvent des structures comme des piles ou des files pour traverser l’arbre. Le principe est de parcourir chaque nœud et d’échanger ses enfants sans recourir à la récursivité.

Pseudocode pour l’approche itérative :

function invertTree(root):
    if root is null:
        return null
    stack = new Stack()
    stack.push(root)
    while not stack.isEmpty():
        node = stack.pop()
        swap(node.left, node.right)
        if node.left is not null:
            stack.push(node.left)
        if node.right is not null:
            stack.push(node.right)
    return root

Implémentation en Python

Mise en place de la classe Node

Pour représenter un arbre binaire en Python, nous utilisons une classe Node :

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

Implémentation de la Fonction d’Inversion Récursive

Voici l’implémentation Python de l’approche récursive :

def invert_tree_recursively(node):
    if node is None:
        return None
    node.left, node.right = node.right, node.left
    invert_tree_recursively(node.left)
    invert_tree_recursively(node.right)
    return node

Test et Validation

# Exemple de test
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

inverted_root = invert_tree_recursively(root)

def print_tree(node):
    if node is not None:
        print(node.val, end=' ')
        print_tree(node.left)
        print_tree(node.right)

print_tree(inverted_root)  # Affiche: 1 3 2 5 4

Implémentation de la Fonction d’Inversion Itérative

L’approche itérative est implémentée comme suit :

def invert_tree_iteratively(root):
    if root is None:
        return None
    stack = [root]
    while stack:
        node = stack.pop()
        node.left, node.right = node.right, node.left
        if node.left is not None:
            stack.append(node.left)
        if node.right is not None:
            stack.append(node.right)
    return root

Test et Validation

# Exemple de test pour l'inversion itérative
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

inverted_root_iter = invert_tree_iteratively(root)

print_tree(inverted_root_iter)  # Affiche: 1 3 2 5 4

Comparaison des Approches Récursive et Itérative

• Récursive :
• Avantages : Plus simple, plus lisible pour ceux qui comprennent la récursivité.
• Inconvénients : Peut entraîner un dépassement de la pile d’appel (Stack Overflow) sur de très grands arbres.
• Itérative :
• Avantages : Évite le risque de dépassement de pile, plus simple à optimiser pour les systèmes limités en mémoire de pile.
• Inconvénients : Peut être moins intuitive à écrire au départ.

En termes de complexité temporelle, les deux approches ont une complexité de O(n), où n est le nombre de nœuds dans l’arbre. Sur le plan spatial, la récursive utilise O(h) pour la pile de récursivité, où h est la hauteur de l’arbre, tandis que l’itérative nécessite O(n) dans le pire des cas pour la pile explicite.

Conseils pour les Entretiens de Codage

• Aborder la question : Commencez par expliquer votre compréhension de l’arbre binaire et du problème d’inversion.
• Expliquer le raisonnement : Parlez de la récursivité et de l’itératif comme deux solutions, et pourquoi vous choisiriez l’une par rapport à l’autre.
• Éviter les pièges : Prêtez attention aux cas où l’arbre est vide ou contient un seul nœud pour démontrer une robustesse dans votre code.

Conclusion

Inverser un arbre binaire est un exercice fondamental qui révèle votre compréhension des arbres et de leur manipulation en Python. La maîtrise de ce concept et sa bonne application lors d’un entretien technique peuvent renforcer votre confiance en vos compétences en programmation.

Ressources Complémentaires

• Tutoriel sur les arbres binaires en Python
• Vidéo explicative sur l’inversion d’arbres binaires

Annexe

Code Complet de l’Exemple d’Inversion avec les Tests

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def invert_tree_recursively(node):
    if node is None:
        return None
    node.left, node.right = node.right, node.left
    invert_tree_recursively(node.left)
    invert_tree_recursively(node.right)
    return node

def invert_tree_iteratively(root):
    if root is None:
        return None
    stack = [root]
    while stack:
        node = stack.pop()
        node.left, node.right = node.right, node.left
        if node.left is not None:
            stack.append(node.left)
        if node.right is not None:
            stack.append(node.right)
    return root

def print_tree(node):
    if node is not None:
        print(node.val, end=' ')
        print_tree(node.left)
        print_tree(node.right)

# Tests
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("Récursive :")
inverted_root = invert_tree_recursively(root)
print_tree(inverted_root)

print("\nItérative :")
inverted_root_iter = invert_tree_iteratively(root)
print_tree(inverted_root_iter)

Glossaire des Termes Clés

• Arbre Binaire : Structure de données avec une racine et deux sous-arbres, chaque sous-arbre étant lui-même un arbre binaire.
• Récursivité : Technique de programmation où une fonction s’appelle elle-même directement ou indirectement.
• Pile : Structure de données où les éléments sont ajoutés et supprimés selon le principe Last In First Out (LIFO).
• File : Structure de données où les éléments sont traités selon le principe First In First Out (FIFO).