General Tree Definitions and Terminology

The list, vector, stack, and queue ADT's / data structures encountered so far are linear.

A tree imposes a hierarchical (and thus nonlinear) structure on a collection of items.

Balanced binary search trees are used for the map container.
- A map is also known as an associative array.
- Indexing using nonintegers, strings for example, as indexes is supported with O(log₂ n) access.

Tree Definition

Trees consist of nodes which are connected by edges.

Nodes represent items of the collection.
Edges connect nodes and represent the relationship between nodes.

A tree is a collection of nodes that originate from a unique starting node called the root.

A tree is defined recursively, some of terms used are defined below.

A single node by itself is a tree.
Given node n and trees T₁, T₂, ..., T_k with roots n₁, n₂, ..., n_k a new tree may be constructed by making n the parent of n₁, n₂, ..., n_k.

Sometimes it is convenient to include the null tree with no nodes.

Tree Terminology

path	A path is a sequence of edges between nodes.
root	The root is the special node from which all other nodes "descend". Each tree has a single root node.
parent of node n	The parent of node n is the unique node with an edge to node n and which is the first node on the path from n to the root. Note: The root is the only node with no parent. Except for the root, each node has one parent.
child of node n	A child of node n is a node for which node n is the next node on the path to the root node. More formally, if the last edge on the path from root r of tree T to node x is (y, x) then node y is the parent of node x and node x is a child of node y. Note: Each node may have 0 or more children.
siblings	Nodes with the same parent are siblings.
ancestor of node n	Any node y on the (unique) path from root r to node n is an ancestor of node n. Every node is an ancestor of itself.
proper ancestor of n	A proper ancestor of n is any node y such that node y is an ancestor of node n and y is not the same node as n.
descendent of n	Any node y for which n is an ancestor of y. Every node is an descendent of itself.
proper descendent of n	A proper descendent of n is any node y for which n is an ancestor of y and y is not the same node as n.
subtrees of node n	Subtrees of node n are the trees whose roots are the children of n.
degree of node n	The degree of node n is the number of children node n has.
leaf node	A leaf node is a node with no children.
external node	An external node is a node with no children (same as a leaf node).
internal node	An internal node is a nonleaf node.
depth of node n	The depth of node n is the length of the path from root to node n.
level d	Level d is the nodes at depth d.
height of tree T	The height of tree T is the largest depth of any node in T. We usually think of height relating to trees and depth relating to nodes however for full trees the terms are sometimes used interchangably.
ordered tree	An ordered tree is a tree in which the children of each node are ordered.
full k-ary tree	A full k-ary tree is a tree in which all leaves have the same depth and all internal nodes have degree k. (The Corman et. al. Algorithms text call this complete.)
binary tree	A binary tree is a tree in which each node has two children, possibly absent, named the left child and the right child. A binary tree is more than a ordered tree of degree 2, in an ordered tree of degree 2 there is no distinguishing of a sole child as left or right.