Unit 4: Trees

Table of Contents

4.1 Basic Concepts of Tree

A graph G = (V, E) consists of a set of vertices V and a set of edges E.

A tree is a connected, undirected graph with no cycles. A graph with no cycles is called acyclic.

4.2 Properties of Trees

Let T be a graph with n vertices. The following are equivalent properties of a tree:

  • T is connected and has no cycles.
  • T has no cycles and has exactly n-1 edges.
  • T is connected and has exactly n-1 edges.
  • There is exactly one unique path between any two vertices in T.
  • T is minimally connected (removing any edge disconnects it).

4.3 Pendant Vertices in a Tree

A pendant vertex (or leaf) is a vertex with a degree of 1.
  • An internal vertex is a vertex with a degree greater than 1.
  • Theorem: Every tree with two or more vertices has at least two pendant vertices.

4.4 Centre of a Tree

The eccentricity e(v) of a vertex v is the length of the longest path from v to any other vertex in the tree.

The radius r(T) of a tree is the minimum eccentricity of all vertices.

The diameter d(T) of a tree is the maximum eccentricity of all vertices (the longest path in the tree).

The centre of a tree T is the set of all vertices with the minimum eccentricity (i.e., all vertices v where e(v) = r(T)).

Finding the Centre: Repeatedly remove all pendant vertices from the tree simultaneously. The vertex or two vertices remaining at the end form the centre. A tree has either one central vertex or two central vertices (which must be adjacent).

4.5 Rooted Binary Trees

A rooted tree is a tree in which one vertex has been designated as the root. This imposes a parent-child hierarchy.

  • Parent: The vertex directly above a given vertex.
  • Child: A vertex directly below a given vertex.
  • Siblings: Vertices with the same parent.
  • Leaf: A vertex with no children (same as pendant vertex, except for a root-only tree).
  • Level: The length of the path from the root (Root is at level 0).
  • Height: The maximum level of any leaf in the tree.
A binary tree is a rooted tree where each internal vertex has at most two children, designated as a left child and a right child. An empty tree is also a binary tree.

4.6 Complete and Extended Binary Trees

Extended Binary Tree (or Full Binary Tree)

A binary tree where every vertex has either 0 or 2 children. The leaves are the 0-child vertices, and the internal nodes are the 2-child vertices.

Complete Binary Tree

A binary tree in which every level, except possibly the last, is completely filled, and all vertices on the last level are as far left as possible.

Key Difference:
  • Full/Extended: Focuses on the number of children (0 or 2). A "lonely" parent with one child is not allowed.
  • Complete: Focuses on the "shape" and filling order. It must be perfectly balanced and filled from left to right.
A tree can be full but not complete, and complete but not full (e.g., if it has a node with one child on the last level).