Example of a tree. 8 is the root. 3 and 10 are children of 8. 1, 13, 4 and 7 are leaves. 10 is an ancestor of 13. 4 is a descendant of 3. 3 is also a descendant of 3 but not a proper descendant. 10 is an ancestor of 10 but not a proper ancestor.

Recursive Definition of a Tree:

Def: A **tree** is a collection of nodes. If the collection can be empty, in which case it is usually denoted as . Otherwise, it consists of a node , called the *root*, and zero or more (sub)-trees each of whose roots are connected by a directed *edge* to the *r*.

Def: Let be the root of a tree with one or more subtrees connected to it. The root of any sub-tree connected to is called a **child** of .

Def: Let be the root of a sub-tree and be the root node the subtree is connected to. is called the **parent** of .

Def: A node in a tree that has no children is referred to as a **leaf** of the tree.

Def: Let and be two nodes in a tree that have the same parent. is called the **sibling** of and vice versa.

Def: A sequence of nodes such that is the parent of for is referred to as a **path**.

Def: The number of edges in a path is called the **length** of the path.

Assertions that have beautiful proofs which you should look up:

- There is a path of length from every node to itself in a tree.
- In a tree, there is exactly one path from the root to each node.

Def: For any node, in a tree, the **depth** of is the length of the unique path from the root of the tree to .

- By definition, the depth of the root is .

Def: Let be any node in a tree. The **height **of is the length of of the longest path from to a leaf.

- By definition, all leaves have a height of .
- The height of a tree is basically the height of the root.

Def: Let and be two nodes in a tree. If a path exists between and then can be called an **ancestor** of . If then is a **proper ancestor **of .

Def: Let and be two nodes in a tree. If a path exists between and then can be called a **descendant** of . If then is a **proper descendant **of .

### Like this:

Like Loading...

*Related*