# Compute size, height and leaf nodes of a tree

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)