This is our boilperplate:

class STree(object):
    def __init__(self, value):
        self.key = value
        self.left = None
        self.right = None

def insert(r, node):
    if node.key < r.key:
        if r.left is None:
            r.left = node
        else:
            insert(r.left, node)
    else:
        if r.right is None:
            r.right = node
        else:
            insert(r.right, node)

Compute the size of a tree

The idea: the size of a tree starting at root is 1 + the size of the left branch + the size of the right branch.
Base case: every time you get to the bottom you return 0, since the size of that subtree is 0.

def compSize(t):
    if t is None:
        return 0
    else:
        return 1 + compSize(t.left) + compSize(t.right)

Compute the height of a tree

The idea: the height of a tree starting at root is 1 + the highest between the left subtree and the right subtree.

if tree is None:
       return 0
    else:
        if self.compHeight(tree.left) > self.compHeight(tree.right):
            return 1 + self.compHeight(tree.left)
        else:
            return 1 + self.compHeight(tree.right)

or more nicely

def maxHeight(t):
    if t is None:
        return 0
    return 1 + max(maxHeight(t.left), maxHeight(t.right))

Again, the algorithm goes deep until a leaf, when it returns max(0, 0) + 1 and then it rolls back up, checking for every level the size of the two subtrees and returning the bigger + 1 one level up.

Another way to “see” what’s happening is:

def maxDepth(t):
    if t is None:
        return 0
    else:
        lDepth = maxDepth(t.left)
        rDepth = maxDepth(t.right)

        if lDepth > rDepth:
            return lDepth + 1
        else:
            return rDepth + 1

Compute the number of leaf nodes in a tree

The idea: the number of leaves starting at root is the number of leves on the left subtree plus the number of leaves in the right subtree. A node is a leaf when it has no children. This algorithm is the same as the one for counting all the nodes of a tree without +1 for every node traversed.

def countLeaves(t):
    if t.left is None and t.right is None:
        return 1
    else:
        return countLeaves(t.left) + countLeaves(t.right)