Rooted and Unrooted Trees in Discrete Mathematics

---

---

Trees are special structures in graph theory and discrete mathematics. Trees are used for representing hierarchies and connections without cycles. The rooted and unrooted trees gives us two different ways to structure and interpret such data.

In this chapter, we will see rooted and unrooted trees. Their characteristics, examples, and applications. We will see the key differences and use examples to highlight each types properties for a better understanding.

Trees in Graph Theory

In graph theory, a tree is a type of connected graph that has no cycles. Each node in the tree represents an entity, and each edge represents a connection between entities.

Trees can be structured in various ways. We can categorize them as either rooted or unrooted depending on their structure and use.

• Unrooted Trees − These are trees with no designated root or starting point. All vertices in unrooted trees are equally important without any hierarchy.
• Rooted Trees − In contrast, a rooted tree designates one vertex as the “root”. This vertex serves as a reference point for organizing all other vertices hierarchically.

Unrooted Trees

Unrooted trees are such structures with no clear hierarchy or direction. This type of tree is common in data representations and does not require a central or “starting” point.

Properties of Unrooted Trees

Let us see some of the properties of unrooted trees. There is node without any specific node serving as a reference. In unrooted trees, each edge represents a connection with no particular order.

Example

Consider a network of cities connected by roads where the only requirement is to connect all cities without any cycles (circular routes). In this case, an unrooted tree could be used to represent the network. Here, each city is connected to at least one other. This ensuring a unique path exists between each pair without loops.

Applications of Unrooted Trees

The unrooted trees are used in scenarios where the structure does not need a hierarchical organization, like −

• Phylogenetic Trees − In biology, unrooted phylogenetic trees represent evolutionary relationships between species without assuming a common ancestor.
• Network Design − Designing computer networks where devices connect without a central hub is another example. In this setup, unrooted trees ensure redundancy and connectivity without a hierarchical structure.

Rooted Trees

We have another type of trees. The rooted trees. It has a clear hierarchy by selecting one vertex as the root. This root acts as an anchor, giving a structured way to organize the vertices.

Structure of Rooted Trees

In a rooted tree, the relationships are organized based on proximity to the root. Each node can have child nodes, and each node except the root has exactly one parent. So there is a parent-child relationship. Like a family tree or an organizational chart.

• Parent-Child Relationship − In a rooted tree, if two vertices are connected by an edge, one is designated as the parent and the other as the child. The child node is "downward" from the parent.
• Siblings − Vertices that share the same parent are siblings.
• Ancestors and Descendants − In this tree structure, nodes can have ancestors (nodes closer to the root) and descendants (nodes further from the root).

Example

Consider a corporate hierarchy where the CEO is at the top. And each department head reports to the CEO, and each department head has employees reporting to them. So the CEO serves as the root. There are department heads as children, and employees under each department head as grandchildren of the root.

Properties of Levels and Depths

Vertices are grouped into levels based on their distance from the root, with the root being at level 0. Each level represents a step down in hierarchy, and the number of levels can determine the trees depth.

Example

Consider a binary tree with three levels. The root is at level 0, its children are at level 1, and so on. This structure is there to give the vertices are systematically organized. They are making it easy to trace paths up or down the hierarchy.

Algorithms and Traversal in Rooted Trees

One of the primary reasons the rooted trees are useful is their ease of traversal. Traversal means visiting each vertex in a specific order.

• Breadth-First Search (BFS) − The basic traversal is BFS. It starts at the root and visits all vertices level by level. This is like reading a book chapter by chapter, where each chapter (or level) is read fully before moving to the next.
• Depth-First Search (DFS) − Another one is It goes as far down one path as possible before backtracking. This method is like exploring a family tree by tracing one lineage from great-grandparents down to current generations before looking at other branches.

Difference between Rooted and Unrooted Trees

Rooted and unrooted trees have several differences because of their structures. Let us see them in the following table −

Real-World Applications of Rooted and Unrooted Trees

Rooted and unrooted trees have many such applications in computer science, biology, and network theory.

• Rooted Trees in Web Design − In web design, rooted trees organize web pages by hierarchy. For example, a website might start with the homepage as the root, with main sections branching off, and each section containing more specific subpages.
• Unrooted Trees in Biology − Unrooted trees often represent relationships in biology, such as between species that share similar characteristics but do not necessarily have a single common ancestor. This helps biologists understand similarities without assuming a direct lineage.

Rooted and Unrooted Trees in Data Organization

When organizing data, rooted and unrooted trees each have distinct advantages −

• Rooted Trees for Data Hierarchies − When data requires a clear organization from top to bottom, such as in XML files. The root provides a starting point. This is making it easy to navigate through structured layers.
• Unrooted Trees for Relational Data − If the data does not require hierarchy, the unrooted trees offer flexibility by showing relationships without emphasizing a central point.

For example, a computer file system uses rooted trees to allow users to follow a single path from the main directory to each file. On the other hand, a social network might use an unrooted tree to make mutual friendships without implying a hierarchy.

Conclusion

In this chapter, we explained the features of rooted and unrooted trees, based on their structures and applications. Rooted trees provide a hierarchical model that is ideal for situations where organization and levels matter.

We also understood how unrooted trees are effective in scenarios without a central point, like phylogenetic trees. In addition, we touched upon some basic traversal techniques in rooted trees such as BFS and DFS.