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 .