Python - Data Structures - Trees

Tree Data Structures in Python

A tree data structure is a non-linear data structure in which a collection of elements known as nodes are connected via edges, resulting in exactly one path between any two nodes.

Like every programming language. In Python a tree, which is a hierarchical data structure, each node is connected by an edge. The tree consists of multiple nodes, with one unique root node serving as the starting point. Trees are often used to represent hierarchical organizations, such as organizational charts or file systems.

The topmost node of the tree is called the root, and the nodes below it are called the child nodes. Each node can have multiple child nodes, and these child nodes can also have their child nodes, forming a recursive structure.

Basic Terminology of Tree

Root Node

The Topmost node of a tree is known as the root node.

Parents Node

A node that has a child node is known as the parent node.

Child Node

A node that is a descendant of another node is known as a child node.

Leaf Node

A node without children is known as a leaf node.

Subtree

A tree consisting of a node and its descendants is known as a subtree.

Height

The number of edges in the longest path from a node to a leaf node.

Depth

The number of edges from the root to a node.

Types of Tree Data Structure

There are three types of tree data structures:

Binary Tree

A binary Tree is defined as a Tree data structure with at most 2 children. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.

Ternary Tree

A Ternary Tree is a tree data structure in which each node has at most three child nodes, usually distinguished as “left”, “mid” and “right”.

N-ary Tree

Generic trees are a collection of nodes where each node is a data structure that consists of records and a list of references to its children(duplicate references are not allowed). Unlike the linked list, each node stores the address of multiple nodes.

Implementation of a Generic Tree in Python

Following is the code implementation of a generic tree in Python:

class Node:
    def __init__(self, data):
        # Data stored in the node
        self.data = data
        # List to store child nodes
        self.children = []

    def add_child(self, child):
        # Add a child to the current node
        self.children.append(child)

    def display(self, level=0):
        # Indentation for hierarchy
        print(" " * level * 4 + str(self.data))
        for child in self.children:
            child.display(level + 1)

root = Node("Root")
child1 = Node("Child 1")
child2 = Node("Child 2")
child3 = Node("Child 3")

root.add_child(child1)
root.add_child(child2)

child1.add_child(Node("Child 1.1"))
child1.add_child(Node("Child 1.2"))

child2.add_child(Node("Child 2.1"))

child3.add_child(Node("Child 3.1"))
child3.add_child(Node("Child 3.2"))

root.add_child(child3)

# Display the tree
root.display()

Tree Traversal Algorithms

Tree traversal algorithms are used to visit each node in the tree. The most common ones include:

• Pre-order Traversal: In this traversal first visit the root node, then traverse the left subtree, followed by the right subtree.
• In-order Traversal: In this traversal, first traverse the left subtree, then visit the root node, and then traverse the right subtree (used in binary search trees for sorted output).
• Post-order Traversal: In this reversal, first traverse the left subtree, then the right subtree, and then visit the root node.
• Level-order Traversal: In this traversal, the nodes will be visited through level by level. It is also known as (Breadth-First-Search).

Use Cases Of Trees

There are the following use cases of tree data structure:

• Hierarchical Data Representation: Organizational hierarchies and file systems, for example, are naturally represented as trees.
• Database indexing: To efficiently search through, add, and remove records from databases, Binary Search Trees (BST) are frequently used.
• Making Decisions: The decision trees used in machine learning for categorization are based on trees, which are fundamental to algorithms for making decisions.
• Web browsers and DOM (Document Object Model): Trees help browsers render web pages more effectively by illustrating the structure of online content.