Any connected graph without a cycle is called a tree. Every edge of a tree is a bridge. In general, a graph without any cycles, whether connected or not, is called a forest. We have already seen some trees:

And many non-trees:

1. Now if u and v are two vertices of a tree G. Then there is exactly one u-v path in G.
   Proof of this is based on G being connected and having more than one path between the same two points would necessarily create a cycle in a connected graph.
2. Any tree that has more than one vertex has at least one vertex of degree 1. (Lemma 11.5.1) Based on trees being finite and circuit free, so there exists a u-v path that terminates (consequently at a degree 1 vertex).
3. Any connected graph with p vertices and q = p -1 edges is a tree. (Theorem 11.5.4)
4. Every tree with p vertices has q = p -1 edges. (Theorem 11.5.2)
5. Any graph with p vertices and fewer than q = p -1 edges is not connected and consequently, not a tree.

A rooted tree has one vertex distinguished from the others. This distinguished vertex is called the root. The level of a vertex is the number of edges (length) of a path from the root to that vertex. The height of a rooted tree is the maximum level of any of its vertices. Given an internal vertex v, the children of v are all those vertices that are adjacent to v and are one level farther away from the root than v. If w is a child of v, then v is called the parent of w and all other vertices in the path from the root to w are ancestors of w, while w is a descendant of each of these vertices. Vertices with the same parent are called siblings.

An m-ary tree is a tree in which each vertex has at most m children. The order in which the children are listed is relevant. In particular, in a binary tree, one must distinguish between the left child and the right child. An internal vertex of a binary tree has at most one left child and one right child. A full binary tree is a binary tree in which every internal vertex has exactly two children. Given any internal vertex v of a binary tree, the left subtree of v is the binary tree whose root is the left child of v and includes all the descendants of v and their edge set. The right subtree is analogous.

Full binary tree: 
Each node is either a leaf or internal node with exactly two non -empty children. (Note: this definition is per the text, a more common definition per recent computer texts is that a FBT is complete -has 2^h terminal vertices.)

Complete Binary Tree: 
If the height of the tree is h, then all levels except possibly level h are completely full. Level h has all nodes filled in to the left side. "In the general case we may number the nodes 1, 2, ..., n; this numbering has the useful property that the father of node k is node ë k/2 û; the sons of node k are nodes 2k and 2k + 1. The terminal nodes are numbers n + 1 through 2n + 1, inclusive." (Knuth, The Art of Computer Programming -Vol 1 Fundamental Algorithms, 1969, p 401)

Example For the following graph complete the following: The root is ___. The left child of b is ____, while i is a _____ child of h. The right subtree of g is ___&__, the left subtree of g is ___&___. Vertex i is a ________ of g, g is an _______ of i. The height of this tree is _____. The root, a, is located at level __ and c is located at level ___. There are eleven vertices and consequently ____ arcs in this tree. Vertices c and f are __________ of b and ___________ to each other.

1. A (complete) full binary tree of height h has 2^h terminal vertices. Consequently, any binary tree of height h has at most 2^h terminal vertices, t. We have t £ 2^h, or equivalently lg t £ h. (Theorem 11.5.6)
2. If k is a positive integer and T is a full binary tree with k internal vertices, the T has a total of 2k + 1 vertices and has k + 1 terminal vertices. (Theorem 11.5.5 read proof on page 678)

Example Is there a full binary tree with 5 internal vertices and 6 terminal vertices? If so, how many total vertices does this tree have?
Solution

Example Is there a binary tree with height 4 and 8 terminal vertices? What is the greatest possible number of terminal vertices in a binary tree of height 4?
Solution

One frequently has to perform operations on trees involving every vertex. In order to perform the operation a recursive tree traversal is required. There are three principal ways to traverse a tree: preorder, inorder, and postorder.

Preorder: NLR

1. (N) Process the root.
2. (L) Search the left subtree in preorder.
3. (R) Search the right subtree in preorder.

Inorder: LNR

1. (L) Search the left subtree in inorder.
2. (N) Process the root.
3. (R) Search the right subtree inorder.

Postorder: LRN

1. (L) Search the left subtree in postorder.
2. (R) Search the right subtree in postorder.
3. (N) Process the root.

The essential difference is the order in which the root is processed: first, middle, or last.

To help with clarity of operation, consider a tree in which the root and internal vertices are arithmetic operators and the terminal vertices are variables:

What is the preorder traversal of this tree? Solution

What is the inorder traversal of this tree? Solution

What is the postorder traversal of this tree? Solution

Let m = 1 and n = 0.5 then determine the value of the expression found in your three solutions above.