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:

Some Facts and Theorems about 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 10.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 10.5.4)
4. Every tree with p vertices has q = p -1 edges. (Theorem 10.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. A vertex of a tree is called a leaf if it has no children. Vertices that have children are called internal vertices. The root is an internal vertex unless it is the only vertex in the graph, in which case it is a leaf. 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.

Let T be a tree. If T has only one or two vertices, then each is called a terminal vertex. If T has at least three vertices, then a vertex of degree 1 in T is called a terminal vertex (or a leaf), and a vertex of degree greater than 1 is called an internal vertex (or a branch vertex).

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, if an internal vertex has two children, one must distinguish between the the first child called the left child and the right child (the second 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 and Complete Binary Trees 

Full binary tree: 
Each node is either a leaf or internal node with exactly two non -empty children. Note: In other words, every node is either a leaf or has two children. For efficiency, any Huffman coding (animation) is a full binary tree.

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.

Two more Theorems

1. 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 10.6.1 read proof on page 697)
2. 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 10.6.2)

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.

Example
What are the preorder, inorder, and postorder expresions for the binary tree in the m-ary example above?
Solution

Applet
http://www.cosc.canterbury.ac.nz/mukundan/dsal/BTree.html