Directed Tree

Definitions

1. A directed tree is a directed graph [math]\displaystyle{ T = (V,A) }[/math] with a designated node [math]\displaystyle{ r \in V }[/math], the root, such that for each node [math]\displaystyle{ v \in V }[/math], there is exactly one path from [math]\displaystyle{ r }[/math] to [math]\displaystyle{ v }[/math] in [math]\displaystyle{ T }[/math].
2. A directed tree [math]\displaystyle{ T = (V,A) }[/math] is called binary if each node's outdegree is at most [math]\displaystyle{ 2 }[/math].
3. The subtree of [math]\displaystyle{ T }[/math] rooted at [math]\displaystyle{ v \in V }[/math] is the subgraph induced by all nodes that are reachable from [math]\displaystyle{ v }[/math] via paths in [math]\displaystyle{ T }[/math] (including [math]\displaystyle{ v }[/math]). In particular, [math]\displaystyle{ T }[/math] is the subtree of [math]\displaystyle{ T }[/math] rooted at [math]\displaystyle{ r }[/math].
4. For an arc [math]\displaystyle{ (v,w) }[/math] in a directed tree, [math]\displaystyle{ w }[/math] is a child of [math]\displaystyle{ v }[/math], and [math]\displaystyle{ v }[/math] is the (unique) parent of [math]\displaystyle{ w }[/math].
5. The height level of a node in a directed tree is recursivley defined as follows:
   1. The height level of the root is [math]\displaystyle{ 0 }[/math]
   2. The height level of any other node is one more than the height level of its parent.
6. The height of an empty tree is [math]\displaystyle{ -1 }[/math]. For a non-empty tree, the height of the tree is the maximum height level of all of its nodes.

Immediate Predecessor and Successor

For a node [math]\displaystyle{ v }[/math] of a binary or multi-way search tree,

1. the immediate predecessor of [math]\displaystyle{ v }[/math] is [math]\displaystyle{ v }[/math]'s immediate predecessor in left-root-right order (if existing), and
2. the immediate successor of [math]\displaystyle{ v }[/math] is [math]\displaystyle{ v }[/math]'s immediate successor in left-root-right order (if existing).