Traversing and measuring a tree

Traversals (pre-order, in-order, post-order) and height

Three ways to read a tree

A tree traversal visits every node in a precise order. The three most common "depth-first" traversals differ only in the position where the root is processed:

pre-order: root, then left subtree, then right subtree;
in-order: left subtree, then root, then right subtree;
post-order: left subtree, then right subtree, then root.

Diagram: the three traversals on the same tree

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

pre-order  (root, left, right) : 8 3 1 6 4 7 10 14 13
in-order   (left, root, right) : 1 3 4 6 7 8 10 13 14   (always sorted !)
post-order (left, right, root) : 1 4 7 6 3 13 14 10 8

The height of a tree

The height of a tree is the length, in number of links, of the longest path between the root and a leaf. A tree reduced to a single node has a height of 0, and an empty tree has a conventional height of -1.

On the tree above, the longest path goes from 8 to 4, 7 or 13 (all at the same depth): for example 8 -> 3 -> 6 -> 4, that is 3 links. The height of this tree is therefore 3.

Implementation in Python

def prefixe(noeud, resultat):
    if noeud:
        resultat.append(noeud.valeur)
        prefixe(noeud.gauche, resultat)
        prefixe(noeud.droit, resultat)
    return resultat

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

Common pitfall