Rooted Trees

Rooted Trees

A rooted tree is a special type of tree in graph theory where one vertex is designated as the "root," and all edges are directed away from or towards the root. Rooted trees are often used to model hierarchical structures, such as organizational charts, file systems, or family trees.

1. Definition of a Tree

Before understanding a rooted tree, it's important to define what a tree is:

• A tree is an undirected graph that is connected and has no cycles. This means that there is exactly one path between any two vertices in the tree.

A rooted tree is a tree where one vertex is chosen as the root, and every edge is directed either towards or away from the root, depending on the convention.

2. Properties of Rooted Trees

Rooted trees have several key properties that distinguish them from general trees:

1. Unique Root: There is one vertex, called the root, that serves as the starting point for all paths in the tree.

2. Parent-Child Relationship: In a rooted tree, every vertex, except the root, has exactly one parent, which is the vertex from which it is connected. Any vertex can have one or more children (subsequent vertices connected to it).

3. Levels and Depth:

   • Level: The level of a vertex is the number of edges on the path from the root to the vertex. The root has a level of 0.
   • Depth: The depth of a vertex is the number of edges from the root to the vertex.
   • Height of the Tree: The height of a rooted tree is the length of the longest path from the root to any leaf (a vertex with no children). It can also be defined as the maximum depth of any node in the tree.

4. Subtree: A subtree of a rooted tree is a tree consisting of a node and all its descendants in the tree. For any node in a rooted tree, the subtree rooted at that node includes the node itself and all of its children, grandchildren, and so on.

5. Leaf: A leaf is a node in the tree that has no children (i.e., a vertex with degree 1 except the root).

3. Representation of Rooted Trees

Rooted trees can be represented in various ways:

1. Adjacency List: An adjacency list is a collection of lists or arrays where each list corresponds to a vertex and contains the list of its children.

   For example, consider the following rooted tree:

       A
      / \
     B   C
    / \
   D   E
   

   The adjacency list representation is:

   • A: [B, C]
   • B: [D, E]
   • C: []
   • D: []
   • E: []

2. Parent Array: Each node has an array where the index represents the node, and the value represents its parent. The root is typically denoted by a special value (such as -1) since it has no parent.

3. Binary Tree Representation: In a binary tree (a specific type of rooted tree where each node has at most two children), each node can have two pointers or references to its left and right children.

4. Types of Rooted Trees

There are several specific types of rooted trees that have additional constraints:

1. Binary Tree:

   • A binary tree is a rooted tree where each vertex has at most two children, typically referred to as the left child and right child.
   • Full Binary Tree: A binary tree in which every node has either 0 or 2 children.
   • Complete Binary Tree: A binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

2. Binary Search Tree (BST):

   • A binary search tree is a binary tree in which the nodes are arranged in such a way that for any node, all values in the left subtree are less than the node’s value, and all values in the right subtree are greater than the node’s value.

3. AVL Tree (Height-Balanced Tree):

   • An AVL tree is a self-balancing binary search tree where the difference between the heights of the left and right subtrees of any node is at most 1. It maintains balance through rotations to ensure efficient searching, insertion, and deletion operations.

4. Trie (Prefix Tree):

   • A Trie is a tree used for storing strings where each node represents a common prefix. It is commonly used in searching and autocomplete systems.

5. Traversing Rooted Trees

Traversal refers to the process of visiting each node in the tree. There are several common methods for traversing a rooted tree:

1. Preorder Traversal (Root, Left, Right):

   • Visit the root first.
   • Then recursively visit the left subtree.
   • Finally, visit the right subtree.

   Example for the tree:

       A
      / \
     B   C
    / \
   D   E
   

   Preorder traversal: A, B, D, E, C

2. Inorder Traversal (Left, Root, Right):

   • Recursively visit the left subtree.
   • Visit the root.
   • Then recursively visit the right subtree.

   Inorder traversal: D, B, E, A, C (typically used in binary search trees to visit nodes in sorted order)

3. Postorder Traversal (Left, Right, Root):

   • Recursively visit the left subtree.
   • Then recursively visit the right subtree.
   • Finally, visit the root.

   Postorder traversal: D, E, B, C, A

4. Level Order Traversal (Breadth-First):

   • Visit all nodes at depth 0, then all nodes at depth 1, and so on. This traversal uses a queue to keep track of nodes to visit.

   Level-order traversal: A, B, C, D, E

6. Applications of Rooted Trees

Rooted trees are useful in many applications:

1. Hierarchical Data: Rooted trees are ideal for representing hierarchical data structures such as organizational charts, classification hierarchies, or folder structures in file systems.

2. Decision Trees: In machine learning, rooted trees are used in decision tree algorithms, where each node represents a decision or a test, and each edge represents the outcome of that test.

3. Binary Search Trees: Binary search trees (BSTs) are used to store data in such a way that allows for efficient searching, insertion, and deletion operations.

4. Expression Parsing: Rooted trees can represent arithmetic expressions, where each node represents an operator or operand, and the tree structure reflects the order of operations.

5. Data Compression (Huffman Encoding): Rooted trees are used in Huffman encoding for optimal data compression. The tree structure is used to assign shorter codes to more frequent elements.

7. Example of a Rooted Tree

Consider a simple rooted tree:

      A
     / \
    B   C
   / \
  D   E

• The root is A.
• The parent of B and C is A.
• The parent of D and E is B.
• The leaves are C, D, and E.

Traversals for the above Tree:

• Preorder Traversal: A, B, D, E, C
• Inorder Traversal: D, B, E, A, C
• Postorder Traversal: D, E, B, C, A
• Level-Order Traversal: A, B, C, D, E

Summary of Key Points

• A rooted tree is a tree in which one vertex is designated as the root, and all other vertices have a parent-child relationship.
• A rooted tree is characterized by parent-child relationships, levels, and depth.
• Special types of rooted trees include binary trees, binary search trees, and tries.
• Traversals of rooted trees include preorder, inorder, postorder, and level-order.
• Rooted trees are widely used in computer science for representing hierarchical data, decision-making processes, and efficient data storage.

Rooted trees provide a structured and efficient way to model and process hierarchical relationships in various applications.