Eksempel: Høyden til et binært tre
Test deg selv
Vi ønsker å definere en rekursiv funksjon som teller antall løvnoder i et binært tre. Hvilke(n) av definisjonene er riktige?
Denne funksjonen teller alle noder i hele treet, og ikke kun løvnodene.
Denne definisjonen dekker ikke alle mulige binære trær. Dersom enten $V$ eller $H$ er et tomt tre, beskriver ikke definisjonen av $M$ hva som skal skje. For eksempel vil ikke funksjonsverdien for $M$ med treet $(❪❫, 1, 2)$ kunne regnes ut. Definisjonen fungerer bare dersom det alltid er slik at $V$ og $H$ er tomme samtidig, og ikke-tomme samtidig.