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".