A **rooted tree** is a free tree in which one of the vertices is distinguished from the others. We call the distinguished vertex the root of the tree. We often refer to a vertex of a rooted tree as a node5 of the tree. Given figure shows a rooted tree on a set of 12 nodes with root 7

Consider a node x in a rooted tree T with root r. We call any node y on the unique simple path from r to x an ancestor of x. If y is an ancestor of x, then x is a descendant of y. (Every node is both an ancestor and a descendant of itself.) If y is an ancestor of x and x ¤ y, then y is a proper ancestor of x and x is a proper descendant of y. The subtree rooted at x is the tree induced by descendants of x, rooted at x. For example, the subtree rooted at node 8 in Figure contains nodes 8, 6, 5, and 9.

If the last edge on the simple path from the root r of a tree T to a node x is .y; x/, then y is the **parent **of x, and x is a **child **of y. The root is the only node in T with no parent. If two nodes have the same parent, they are **siblings**. A node with no children is a **leaf **or **external node**. A nonleaf node is an **internal node**.

An ordered tree is a rooted tree in which the children of each node are ordered. That is, if a node has k children, then there is a first child, a second child, . . . , and a kth child. The two trees in Figure B.6 are different when considered to be ordered trees, but the same when considered to be just rooted trees.