Tree

A tree is a finite set made up of n nodes, where n ≥ 0.

When n = 0, the structure is called an empty tree.

For any non-empty tree, the following conditions hold:

• There is one special node called the root, usually denoted as root.
• All remaining nodes can be divided into m mutually disjoint finite sets T₁, T₂, …, Tₘ, where m > 0.
• Each of these finite sets is itself a tree, and is called a subtree of the original tree.

A valid tree has several important structural characteristics:

• Subtrees do not overlap with one another.
• Except for the root node, every node has exactly one parent node.
• A tree with N nodes has exactly N - 1 edges.

In this sense, a tree can be understood as one of the minimal ways to keep all nodes connected.

Basic terminology

Degree of a node: the number of subtrees of that node.

Degree of a tree: the maximum degree among all nodes in the tree.

Leaf node: a node whose degree is 0.

Parent node: if a node has subtrees, it is the parent of the root nodes of those subtrees.

Child node: if node A is the parent of node B, then B is a child of A.

Sibling nodes: nodes that share the same parent are siblings.

Path and path length: a path from node n₁ to node nₖ is a sequence of nodes n₁, n₂, …, nₖ, where each nᵢ is the parent of nᵢ₊₁. The number of edges contained in the path is called the path length.

Ancestor: every node on the path from the root to a given node is an ancestor of that node.

Descendant: all nodes contained in the subtree of a given node are descendants of that node.

Level of a node: the root node is defined to be on level 1. For any other node, its level is the level of its parent plus 1.

Depth of a tree: the maximum level among all nodes in the tree is the depth of the tree.

Binary tree

A binary tree is a tree structure in which each node has at most two child subtrees. Common forms include skewed binary trees, perfect binary trees, and complete binary trees.

Complete binary trees

For a complete binary tree, nodes are filled level by level, and the nodes on the last level are arranged as far left as possible.

The structure above is a complete binary tree.

The structure above is not a complete binary tree because there is a break at node D.

Properties of binary trees

• The maximum number of nodes on level i of a binary tree is 2^i - 1, where i ≥ 1.
• A binary tree with depth k has at most (2^k) - 1 nodes in total, where k ≥ 1.
• For any non-empty binary tree T, if n₀ represents the number of leaf nodes and n₂ represents the number of non-leaf nodes with degree 2, then:

n₀ = n₂ + 1

The third property can be derived from the relationship between the total number of nodes and the total number of edges.

If a binary tree contains nodes of degree 0, degree 1, and degree 2, then the total number of nodes is:

n₀ + n₁ + n₂

Since a tree with N nodes has N - 1 edges, the number of edges can be written as:

n₀ + n₁ + n₂ - 1

The same edge count can also be obtained by summing the degrees of all nodes:

0 * n₀ + 1 * n₁ + 2 * n₂

Therefore:

n₀ + n₁ + n₂ - 1 = 0 * n₀ + 1 * n₁ + 2 * n₂

After simplification:

n₀ = n₂ + 1