Trees

The structural "shape" of a tree is intrinsically hierarchical, so trees are generally the structure of choice whenever we wish to model a hierarchical arrangement of any kind. Some things that fall into this category are:

• the personnel reporting structure in most organizations
• the directory structure of a computer operating system
• a web site
• a book, with its "parts", "chapters", "sections" and "subsections"
• expression evaluation in compiler design

Some basic tree terminology

The terminology used for describing tree data structures is a very curious mixture of the mathematical, the genealogical, and the botanical. (B. R. Preiss)

child, parent, sibling, ancestor, descendant

A directed edge points from the (unique) parent node to a (not necessarily unique, and often not unique) child node. An ancestor node of a node is either the parent of the node or the parent of some ancestor of the node. A descendant of a node is either a child of the node or a child of some descendant of the node. Both of these definitions are, of course, recursive. Nodes with the same parent are called siblings. The terms grandparent and grandchild are occasionally used as well, and have the obvious meanings, but this is perhaps overdoing the terminology a bit.

leaf nodes (or external nodes), internal nodes (or interior nodes)

A leaf node (also called an external node) is a node with no children. All other nodes are called internal nodes, or interior nodes.

subtree

Each node in a tree may be considered as the root of some subtree, which consists of the node itself, together with all descendants of that node.

degree of a node

The degree of a node is the number of non-empty subtrees that it has. It follows from this that

• A node with degree 0 is a leaf.
• Any node with positive degree is an internal node.
• The maximum degree that a node in a binary tree (see below) can have is 2.

size of a node, size of a tree

The size of a node is the number of descendants a node has, including the node itself. The size of the root node is also called the size of the tree.

depth of a node (or level of a node)

The depth of a node (also called the level of the node) is the length of the path from the root to that node. Hence the depth, or level, of the root node is 0, and in a tree with k+1 levels, the levels will be numbered from 0 to k. Another way of looking at this is that the level on which a node resides is the same as the path length from the root to that node.

height of a node, height of a tree

The height of a node is the length of the path from that node to the deepest leaf that can be reached from that node. For this reason the height of the root node is also called the height of the (entire) tree.

Binary Trees

binary tree

A binary tree is a tree in which each node is limited to 0, 1 or 2 children.

left child, right child

The two (possible) children of a binary tree have an order associated with them. One is called the left child and the other the right child. In diagrams of binary trees we show, for obvious reasons, the children of any node in the positions suggested by their names.

left subtree, right subtree

The left child of a given node in a binary tree is the root of another binary tree called the left subtree of that node. Similarly, the right child of a given node is the root of another binary tree called the right subtree of that node.

full binary tree

A binary tree is said to be full if all the leaves are on the same level and every non-leaf node has exactly two children.

complete binary tree

A binary tree is said to be complete if exactly one of the following two conditions is satisfied:

• It is full.
• Or, it is full through to the next-to-last level, with all the leaves on the last level being as far to the left as possible.

Traversals of binary trees

There are many ways in which we can traverse a binary tree (i.e., "visit all nodes of" the binary tree), and many reasons why we might wish to do so. Here are some of the standard traversal routes, each one starting at the root:

preorder (VLR)

First visit the node itself, then visit all nodes in the left subtree of the node, then visit all nodes in the right subtree of the node.

inorder (LVR)

First visit all the nodes in the left subtree of the node, then visit the node itself, then visit all nodes in the right subtree of the node.

postorder (LRV)

First visit all nodes in the left subtree of the node, then visit all the nodes in the right subtree of the node, then visit the node itself.

level-order

Visit all nodes at each (increasing) level, in left-to-right order.

You will note that the first three traversals above are labelled according to the order in which a node is processed, or "visited" (V), relative to the nodes in its left subtree (L) and its right subtree (R). If V is done first, it's preorder, if V is done last it's postorder, and if V is done in the middle, it's inorder. We also follow the convention of always processing the left subtree before the right subtree, which means that we ignore the other three traversal possibilities (VRL, RVL, and RLV). This appears to be universal practice.

Special kinds of binary trees

Binary trees are useful models in many different situations. In addition to binary search trees that were discussed in the previous course, two of the more common ones are these:

binary expression tree

A binary expression tree is a binary tree that stores an expression (such as an arithmetic expression) in such a way that each leaf node contains an operand of the expression, and each interior node contains an operator of the expression.

heap

A heap is a complete binary tree, each of whose nodes contains a key which is greater than or equal to the key in each of its children. Actually, this is technically a "maximum heap"; if we replace "greater than or equal to" with "less than or equal to", we get the definition of a "minimum heap". Thus a heap satisfies two properties: a "shape property" and an "order property". [Note that this heap is not the "free store" heap, but something entirely different.]