CMSC--202 , Section Computer Science II for Majors
Fall 1997 11 October 1997 Handout -- Trees

This handout discusses trees in general, not just binary trees.

Basics

• Trees are formed from nodes and edges. Nodes are sometimes called vertices. Edges are sometimes called branches.
• Nodes may have a number of properties including value and label.
• Edges are used to relate nodes to each other. In a tree, this relation is called ``parenthood.''
• An edge {a,b} between nodes a and b establishes a as the parent of b. Also, b is called a child of a.
• Although edges are usually drawn as simple lines, they are really directed from parent to child. In tree drawings, this is top-to-bottom.

• Informal Definition: a tree is a collection of nodes, one of which is distinguished as ``root,'' along with a relation (``parenthood'') that is shown by edges.
• Formal Definition: This definition is ``recursive'' in that it defines tree in terms of itself. The definition is also ``constructive'' in that it describes how to construct a tree.
  1. A single node is a tree. It is ``root.''
  2. Suppose N is a node and are trees with roots , respectively. We can construct a new tree T by making N be the parent of the nodes . Then, N is the root of T and are subtrees.

• A node is either internal or it is a leaf.
• A leaf is a node that has no children.
• Every node in a tree (except root) has exactly one parent.
• The degree of a node is the number of children it can have.
• The degree of a tree is the maximum degree of all of its nodes.

Paths and Levels

• Definition: A path is a sequence of nodes such that node is the parent of node for all .

• Definition: The length of a path is the number of edges on the path (one less than the number of nodes).

• Definition: The descendents of a node are all the nodes that are on some path from the node to any leaf.

• Definition: The ancestors of a node are all the nodes that are on the path from the node to the root.

• Definition: The depth of a node is the length of the path from root to the node. The depth of a node is sometimes called its level.

• Definition: The height of a node is the length of the longest path from the node to a leaf.

• Definition: the height of a tree is the height of its root.

• The nodes Y, Z, U, V, and W are leaf nodes.
• The nodes R, S, T, and X are internal nodes.
• The degree of node T is 3. The degree of node S is 1.
• The depth of node X is 2. The depth of node Z is 3.
• The height of node Z is zero. The height of node S is 2. The height of node R is 3.
• The height of the tree is the same as the height of its root R. Therefore the height of the tree is 3.
• The sequence of nodes R,S,X is a path.
• The sequence of nodes R,X,Y is not a path because the sequence does not satisfy the ``parenthood'' property (R is not the parent of X).

Binary Trees

• Definition: A binary tree is a tree in which each node has degree of exactly 2 and the children of each node are distinguished as ``left'' and ``right.'' Some of the children of a node may be empty.
• Formal Definition: A binary tree is:
  1. either empty, or
  2. it is a node that has a left and a right subtree, each of which is a binary tree.
• Definition: A full binary tree (FBT) is a binary tree in which each node has exactly 2 non-empty children or exactly two empty children, and all the leaves are on the same level. (Note that this definition differs from the text definition).
• Definition: A complete binary tree (CBT) is a FBT except, perhaps, that the deepest level may not be completely filled. If not completely filled, it is filled from left-to-right.
• A FBT is a CBT, but not vice-versa.

Examples

• Note that in a FBT, the number of nodes at level i is .

• The above tree is not a CBT because the deepest level is not filled from left-to-right.