Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Rooted Tree Definitions

From the module definitions sheet:

  • a rooted tree has one root node, and every other node has a unique parent
  • the children of are the nodes whose parent is , a leaf has no children, and an internal node is not a leaf
  • is an ancestor of if there is a chain of parents from down to (the sheet counts as its own ancestor, a proper ancestor excludes it)
  • the subtree rooted at is together with all its descendants

Depth, Height and Levels

Definitions:

  • depth of the root is , and the depth of any other node is one more than the depth of its parent
  • height of a tree is the maximum depth of its nodes, i.e. the maximum number of ancestors of any node
  • the -th level is the set of all nodes with depth
  • an empty tree has height and a single node has height

The height can be computed with the same recursion as the node structure suggests, where T.left and T.right are subtrees:

def height(T):
    if T is None:
        return -1                      # empty tree
    return 1 + max(height(T.left), height(T.right))

Binary Tree

A binary tree is a rooted tree where every node has at most 2 children: at most one left child v.left and at most one right child v.right. A node with one child must still say whether it is the left or the right child. "Binary tree" is one term and always means a rooted tree.

Complete Binary Tree

A complete binary tree satisfies:

  • every level is completely filled, except perhaps the last level, so level has nodes for less than the height
  • the nodes on the last level are as far to the left as possible

A complete binary tree with height has between and nodes, so . This is why a complete tree fits neatly in an array and why heap operations are .

Traversals as Definitions

The three traversals of start at T.root and are defined recursively, with null giving the empty list []:

Knowing these exact recursive forms is safer than remembering only "root, left, right".