Tree

Tags

math

Is a connected graph with no cycles. Algorithmically a tree is recursively [see page 4, defined] as a finite set of nodes such that either: The tree is empty (no nodes) or it is composed of a root node, and one or more sub-trees.

A leaf node is a node that has no children. Any other nodes in the tree is an internal node.

The height of a node is defined as the length of the longest path from that node to a leaf node.

\begin{align} H(N) = \begin{cases}

0 & \text{If node is empty} \\\\
1 + H(N.\text{left}) + H(N.\text{right}) & \text{Otherwise}

\end{cases} \end{align}

The height of a tree is the height of the root node of that tree.