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)