Insertion and search in a BST

Searching: follow the right path

Searching for a value in a BST means descending from the root, choosing at each node to go left (if the value sought is smaller) or right (if it is greater), until you find the value or hit an empty subtree.

Diagram: searching for 7

                   (8)
                  /   \
               (3)     10
               / \        \
              1  (6)       14
                 / \       /
                4  (7)   13

path followed : 8 -> 3 -> 6 -> 7
   7 < 8  : go left
   7 > 3  : go right
   7 > 6  : go right
   7 = 7  : found !

Inserting: same logic, until an empty spot

Inserting a value follows exactly the same path as the search, but when you reach an empty subtree, you create the new node there.

Diagram: inserting 5

descent :
   5 < 8  : go left               (node 8)
   5 > 3  : go right              (node 3)
   5 < 6  : go left               (node 6)
   5 > 4  : right subtree empty, insert here (node 4)

after insertion :
                    8
                  /   \
                 3     10
                / \       \
               1   6        14
                  / \      /
                 4   7    13
                  \
                   5

Implementation in Python

class Noeud:
    def __init__(self, valeur):
        self.valeur = valeur
        self.gauche = None
        self.droit = None

def inserer(noeud, valeur):
    if noeud is None:
        return Noeud(valeur)
    if valeur < noeud.valeur:
        noeud.gauche = inserer(noeud.gauche, valeur)
    else:
        noeud.droit = inserer(noeud.droit, valeur)
    return noeud

def rechercher(noeud, valeur):
    if noeud is None:
        return False
    if valeur == noeud.valeur:
        return True
    if valeur < noeud.valeur:
        return rechercher(noeud.gauche, valeur)
    return rechercher(noeud.droit, valeur)

Common pitfall

Forgetting to reassign the result of the recursive call (noeud.gauche = inserer(...)) is a very frequent mistake: without this reassignment, the new node is indeed created, but never actually attached to the existing tree.