tree definitions

A tree is a set of nodes and edges (not necessarily a root). Edges connect nodes together.

Between any two nodes there is only one path (that is what makes a tree special).

Other Definitions

A path is a connected sequence of edges. No circular path or loop is legal in trees.

To convert any tree into a rooted tree, designate any node as the *root*.

Rooted tree: one distinguished node is the *root*.

Every node c, except the root, has one parent (p), which is the first node on path from c to root, therefore, c is p's child. The root has no parent. A node can have any # of children.

leaf: node with no children.

siblings: nodes with then same parents.

ancestors of a node n: nodes on the path from n to the root (including n itself).

if a is an ancestor of b, the b is a descendant of a.

length of a path: number of edges in a path, from one node to another, including itself (0).

depth of a node: length of path from n to root (depth of root is zero).

height of a node n: length of a path from n to its deepest descendant (height of any leaf is zero).

height of a tree: height of the root.

subtree rooted at n: the tree formed by n and all of its descendants.

a binary tree: no nodes have more than 2 children, thus binary. every child is a right or a left child, even if it is the only child.

Tree Traversals

A traversal is a manner of visiting each node once.

Pre-order traversal

visits each node before recursively visiting its children, L to R. Root is visited first (Root - Left - Right).

Each node is visited only once. so a preorder traversal takes O(n) time, where n is the number of nodes in a tree.

Pre-order is good for printing the structure of a directory.

Post-order traversal

visits each node children (left to right) before the node itself (Left - Right -Root).

Is a natural way to sum total disk space in directories, because you need to know the subdirectoriessize before you can figure out the size of directories are.

In-order traversal

Only defined in binary trees. visits root in the middle (Left - Root - Right). Natural way to write an expression.