Introduction to trees

This learning module has many interactive demos. It is easier to work with them on a larger screen. Bookmark and revisit if you are currently on a small screen device.

\(\DeclareMathOperator*{\argmax}{arg\,max} \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator*{\asterisk}{\ast} \newcommand{\sup}{\text{sup}} \newcommand{\inf}{\text{inf}} \newcommand{\min}{\text{min}\;} \newcommand{\max}{\text{max}\;} \newcommand{\maxunder}[1]{\underset{#1}{\max}} \newcommand{\minunder}[1]{\underset{#1}{\min}} \newcommand{\real}{\mathbb{R}} \newcommand{\natural}{\mathbb{N}} \newcommand{\integer}{\mathbb{Z}} \newcommand{\rational}{\mathbb{Q}} \newcommand{\irrational}{\mathbb{I}} \newcommand{\complex}{\mathbb{C}} \newcommand{\cardinality}[1]{|#1|} \newcommand{\vec}[1]{\mathbf{#1}} \newcommand{\mat}[1]{\mathbf{#1}} \newcommand{\star}[1]{#1^*} \newcommand{\inv}[1]{#1^{-1}} \newcommand{\indicator}[1]{\mathcal{I}(#1)} \renewcommand{\BigO}[1]{\mathcal{O}(#1)} \renewcommand{\BigOsymbol}{\mathcal{O}} \renewcommand{\smallo}[1]{\mathcal{o}(#1)} \renewcommand{\smallosymbol}[1]{\mathcal{o}} \newcommand{\set}[1]{\mathbb{#1}} \newcommand{\complement}[1]{#1^c} \newcommand{\powerset}[1]{\mathcal{P}(#1)} \newcommand{\setdiff}{\setminus} \newcommand{\setsymmdiff}{\oplus} \newcommand{\dash}[1]{#1^{'}} \newcommand{\permutation}[2]{{}_{#1} \mathrm{ P }_{#2}} \newcommand{\combination}[2]{{}_{#1} \mathrm{ C }_{#2}} \newcommand{\prob}[1]{P(#1)} \newcommand{\pmf}[1]{P(#1)} \newcommand{\pdf}[1]{p(#1)} \newcommand{\cdf}[1]{F(#1)} \newcommand{\expect}[2]{E_{#1}\left[#2\right]} \newcommand{\entropy}[1]{\mathcal{H}\left[#1\right]} \newcommand{\expe}[1]{\mathrm{e}^{#1}} \newcommand{\textexp}[1]{\text{exp}\left(#1\right)} \def\independent{\perp\!\!\!\perp} \def\notindependent{\not\!\independent} \newcommand{\yhat}{\hat{y}} \newcommand{\vs}{\vec{s}} \newcommand{\vt}{\vec{t}} \newcommand{\vu}{\vec{u}} \newcommand{\vv}{\vec{v}} \newcommand{\vw}{\vec{w}} \newcommand{\vx}{\vec{x}} \newcommand{\vy}{\vec{y}} \newcommand{\vz}{\vec{z}} \newcommand{\va}{\vec{a}} \newcommand{\vb}{\vec{b}} \newcommand{\vc}{\vec{c}} \newcommand{\vd}{\vec{d}} \newcommand{\ve}{\vec{e}} \newcommand{\vg}{\vec{g}} \newcommand{\vh}{\vec{h}} \newcommand{\vi}{\vec{i}} \newcommand{\vk}{\vec{k}} \newcommand{\vo}{\vec{o}} \newcommand{\vp}{\vec{p}} \newcommand{\vq}{\vec{q}} \newcommand{\vr}{\vec{r}} \newcommand{\vs}{\vec{s}} \newcommand{\vmu}{\vec{\mu}} \newcommand{\vsigma}{\vec{\sigma}} \newcommand{\vphi}{\vec{\phi}} \newcommand{\vtau}{\vec{\tau}} \newcommand{\vtheta}{\vec{\theta}} \newcommand{\mA}{\mat{A}} \newcommand{\mB}{\mat{B}} \newcommand{\mC}{\mat{C}} \newcommand{\mD}{\mat{D}} \newcommand{\mE}{\mat{E}} \newcommand{\mH}{\mat{H}} \newcommand{\mK}{\mat{K}} \newcommand{\mP}{\mat{P}} \newcommand{\mQ}{\mat{Q}} \newcommand{\mR}{\mat{R}} \newcommand{\mS}{\mat{S}} \newcommand{\mU}{\mat{U}} \newcommand{\mV}{\mat{V}} \newcommand{\mW}{\mat{W}} \newcommand{\mX}{\mat{X}} \newcommand{\mY}{\mat{Y}} \newcommand{\mZ}{\mat{Z}} \newcommand{\mI}{\mat{I}} \newcommand{\mLambda}{\mat{\Lambda}} \newcommand{\mSigma}{\mat{\Sigma}} \newcommand{\mTheta}{\mat{\theta}} \newcommand{\setsymb}[1]{#1} \newcommand{\sA}{\setsymb{A}} \newcommand{\sB}{\setsymb{B}} \newcommand{\sC}{\setsymb{C}} \newcommand{\sO}{\setsymb{O}} \newcommand{\sP}{\setsymb{P}} \newcommand{\sQ}{\setsymb{Q}} \newcommand{\sH}{\setsymb{H}} \newcommand{\sX}{\setsymb{X}} \newcommand{\sY}{\setsymb{Y}} \newcommand{\norm}[2]{||{#1}||_{#2}} \newcommand{\infnorm}[1]{\norm{#1}{\infty}} \newcommand{\fillinblank}{\text{ }\underline{\text{ ? }}\text{ }} \newcommand{\lbrace}{\left\{} \newcommand{\rbrace}{\right\}} \newcommand{\set}[1]{\lbrace #1 \rbrace} \newcommand{\seq}[1]{\left( #1 \right)} \newcommand{\ndim}{N} \newcommand{\ndimsmall}{n} \newcommand{\dataset}{\mathbb{D}} \newcommand{\ndata}{D} \newcommand{\ndatasmall}{d} \newcommand{\labeledset}{\mathbb{L}} \newcommand{\nlabeled}{L} \newcommand{\nlabeledsmall}{l} \newcommand{\unlabeledset}{\mathbb{U}} \newcommand{\nunlabeled}{U} \newcommand{\nunlabeledsmall}{u} \newcommand{\nclass}{M} \newcommand{\nclasssmall}{m} \newcommand{\loss}{\mathcal{L}} \newcommand{\sign}{\text{sign}} \newcommand{\Gauss}{\mathcal{N}} \newcommand{\hadamard}{\circ} \newcommand{\doh}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\dox}[1]{\doh{#1}{x}} \newcommand{\doy}[1]{\doh{#1}{y}} \newcommand{\doxx}[1]{\doh{#1}{x^2}} \newcommand{\doyy}[1]{\doh{#1}{y^2}} \newcommand{\doxy}[1]{\frac{\partial #1}{\partial x \partial y}} \newcommand{\doyx}[1]{\frac{\partial #1}{\partial y \partial x}} \newcommand{\qed}{\tag*{$\blacksquare$}}\)

        Trees
        Foundations of mathematics
      

Introduction

Trees are specialized graphs with parent-child relationships between nodes. A solid understanding of trees is essential to tackle advanced subjects such as a algorithms.

Tree

A tree is a connected undirected graph with no simple circuits In other words, an undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.

In many trees, one particular vertex is known as a root and relationships within the tree are assigned with respect to the root vertex. A tree with a root is known as a rooted tree. A rooted tree is a directed graph such that a directed edge indicates a parent-child relationship. If there is a directed edge from a vertex $ a $ to vertex $ b $ in a rooted tree, then the vertex $ a $ is known as the parent of the child $ b $. Since all relationships begin at the root, the root has no parents.

Vertices with the same parent are known as siblings. The ancestors of a vertex $ a $ are all the vertices in the path from the root to the vertex $ a $. Conversely, the descendents of a vertex $ b $ are all the vertices that have the vertex $ b $ as their ancestor.

A vertex in a rooted tree is called a leaf if it does not have any children. Vertices that have children are known as internal vertices. The root is also an internal vertex, unless it is the only vertex in the graph, in which case, it is a leaf.

If $ a $ is a vertex in a tree, then the subtree with $ a $ at its root is the subgraph of the tree consisting of $ a $ and its descendents and all the edges incident to these descendents.

$m$-ary tree

A rooted tree is known as an $ m $-ary tree if every internal vertex has no more than $ m $ children. The tree is called a full $ m $-ary tree if every internal vertex has exactly $ m $ children. An $ m $-ary tree with $ m = 2 $ is known as a binary tree.

Number of edges in a tree

A tree with $ n $ vertices has exactly $ n - 1 $ edges.

Proof

The above statement can be proven with mathematical induction.

Base step: Easy to see that it is true when $ n = 1 $, since there are no edges in such a tree. For $ n = 2 $, there is exactly one edge connecting the two vertices.

Inductive hypothesis: Suppose it is true for $ n = k $. This means, there are $ k - 1 $ edges in a tree with $ k $ vertices.

Inductive step: Then, an additional vertex can be added to the tree by introducing one more edge to connect the new vertex to an existing one.

Thus, for a tree with $ k + 1 $ vertices, there are $ k - 1 + 1 = k $ edges.

$$\qed$$

In fact, any connected graph with $ n $ vertices and $ n-1 $ edges is a tree. This is because $ n - 1 $ edges are the minimum number of edges required for a connected graph with $ n $ nodes. Removal of any edge renders the graph disconnected, implying that there are no circuits in a graph with $ n - 1$ edges. Thus, it must be a tree.

Properties of trees

Some useful properties of trees

A tree with $ n $ vertices has $ n - 1 $ edges
A full $ m $-ary tree with $ i $ internal vertices contains $ n = mi + 1 $ vertices
There are at most $ m^h $ leaves in an $ m $-ary tree of height $ h $.
If an $ m $-ary tree of height $ h $ has $ l $ leaves, then $ h \ge \left\lceil \log_m l \right\rceil $. The equality occurs when the tree is full and balanced.

Universal address system

For an ordered rooted tree, the universal address system is labeling procedure that works as follows

Label the root as $ 0 $
Label the $ k $ children of the root from left to right as $ 1, 2, \ldots, k $.
For a vertex that has been labeled $ a $, label its children $ k_a $ from left to right as $ a.1, a.2, \ldots, a.k_v $.

Thus, the universal address system provides a lexicographic ordering of the vertices of a tree in the form of their labels.

Preorder traversal

Let $ T $ be an ordered tree rooted at $ r $. If $ r $ is the only vertex in the tree, then preorder traversal involves visiting $ r $.

Otherwise, if $ T_1, T_2, T_n $ are the subtrees of $ T $ at $ r $ from left to right, then preorder traversal involves visiting $ r $ followed by the preorder traversal of $ T_1 $, then $ T_2 $, and so on, finally culminating in traversing $ T_n $ in preorder.

Note that in a preorder traversal, the root is visited before any of its subtrees are traversed.

In the above figure, we have numbered the order of traversal of each of the nodes, starting at the root.

Inorder traversal

Let $ T $ be an ordered tree rooted at $ r $. If $ r $ is the only vertex in the tree, then inorder traversal involves visiting $ r $.

Otherwise, if $ T_1, T_2, T_n $ are the subtrees of $ T $ at $ r $ from left to right, then inorder traversal involves inorder traversal of $ T_1 $, followed by visiting $ r $, and then the inorder traversal of $ T_2 $, then $ T_3 $, and so on, finally culminating in traversing $ T_n $ in inorder.

Note that in an inorder traversal, the root is visited after its first subtree has been traversed.

In the above figure, we have numbered the order of traversal of each of the nodes, starting at the root.

Postorder traversal

Let $ T $ be an ordered tree rooted at $ r $. If $ r $ is the only vertex in the tree, then postorder traversal involves visiting $ r $.

Otherwise, if $ T_1, T_2, T_n $ are the subtrees of $ T $ at $ r $ from left to right, then postorder traversal postorder traversal of $ T_1 $, then the postorder traversal of $ T_2 $, then $ T_3 $, and so on until traversing $ T_n $ in postorder, finally ending with the visit to $ r $.

Note that in a postorder traversal, the root is visited after all of its subtrees are traversed.

In the above figure, we have numbered the order of traversal of each of the nodes, starting at the root.

Spanning tree

A spanning tree of a simple graph $ G $ is a subgraph of $ G $ that is a tree containing every vertex of the graph $ G $.

A simple graph is connected if and only if it has a spanning tree.

Two algorithms are popular for constructing a spanning tree of a connected graph. The breadth-first search algorithm starts at a node then visits all its children, followed by their children, till the entire graph has been traversed. The depth-first search algorithm starts at a node and completely traverses its first subtree, followed by the next subtree, till the entire graph has been traversed. Since the depth-first search algorithm goes back to traverse another subtree of the same parent, it is also known as backtracking.

Minimum spanning tree

A minimum spanning tree in a connected weighted graph is a spanning tree that has the smallest possible sum of weights of its edges.

Prim's algorithm

The Prim's algorithm for finding a minimum spanning tree is a greedy algorithm that starts by adding the edge with the smallest weight to the spanning tree. Then it adds another edge with the lowest weight among the weights that are incident on the vertices already in the spanning that does not lead to a circuit. It stops when $ n - 1 $ such edges have been added.

It can be proven that the Prim's algorithm produces a minimum spanning tree for any connected weighted graph.

Kruskal's algorithm

The Kruskal's algorithm for finding a minimum spanning tree is a greedy algorithm that successively adds edges with minimum weight to the spanning tree that do not form a simple circuit with those edges that are not already in the spanning tree, until $ n - 1 $ edges have been added to the tree.

It can be proven that Kruskal's algorithm produces a minimum spanning tree for any connected weighted graph.

Next-article

If you haven't already studied graphs, we recommend that you study these generalization of the tree concept to directed and undirected graphs. Else, you can check out other subjects in our curriculum.

Please support us

Help us create more engaging and effective content and keep it free of paywalls and advertisements!

Please donate

Let's connect

Please share your comments, questions, encouragement, and feedback.

Trees

Foundations of mathematics

Introduction

Tree

\(m\)-ary tree

Number of edges in a tree

Proof

Properties of trees

Universal address system

Preorder traversal

Inorder traversal

Postorder traversal

Spanning tree

Minimum spanning tree

Prim's algorithm

Kruskal's algorithm

Next-article

Please support us

Let's connect