# 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)