# DSA Week 2 - II Non-Linear Data Structures Explained: A Beginner's Guide

## Non-Linear Data Structure

Non-linear data structures are those in which data elements are not arranged in a sequential order. Instead, they are organized in a hierarchical or interconnected manner, allowing more complex relationships among the data elements. Non-linear data structures are essential for representing relationships and hierarchies in various domains such as computer networks, databases, and artificial intelligence.

### Key Non-Linear Data Structures

![](https://www.simplilearn.com/ice9/free_resources_article_thumb/Trees-Soni/what-is-tree.png align="center")

1. **Trees**
    
    A tree is a hierarchical structure consisting of nodes, with one node as the root and others as its children. Each node can have zero or more child nodes.
    
    **Characteristics**:
    
    * **Root**: The topmost node.
        
    * **Parent**: A node that has child nodes.
        
    * **Child**: A node that has a parent node.
        
    * **Leaf**: A node with no children.
        
    * **Depth**: The length of the path from the root to a node.
        
    * **Height**: The length of the path from a node to the deepest leaf.
        
    
    **Types of Trees**:
    
    * **Binary Tree**: Each node has at most two children (left and right).
        
    * **Binary Search Tree (BST)**: A binary tree where the left child contains values less than the parent node, and the right child contains values greater than the parent node.
        
    * **AVL Tree**: A self-balancing binary search tree where the difference in heights of left and right subtrees is at most one.
        
    * **Heap**: A special tree-based data structure that satisfies the heap property. It can be a max heap or a min heap.
        
    * **Trie**: A tree-like data structure used to store associative data structures.
        
    
    **Python Example of a Binary Tree**:
    
    ```python
    class TreeNode:
        def __init__(self, value):
            self.value = value
            self.left = None
            self.right = None
    
    def inorder_traversal(root):
        if root:
            inorder_traversal(root.left)
            print(root.value, end=' ')
            inorder_traversal(root.right)
    
    # Create nodes
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    
    # Inorder traversal
    inorder_traversal(root)  # Output: 4 2 5 1 3
    ```
    
    ![](https://generalducky.github.io/images/Pic1.PNG align="center")
    
2. **Graphs**
    
    A graph is a collection of nodes (vertices) connected by edges. Graphs can represent various systems such as social networks, transportation networks, and dependency structures.
    
    **Characteristics**:
    
    * **Vertex (Node)**: Fundamental unit of a graph.
        
    * **Edge (Link)**: Connection between two vertices.
        
    * **Directed Graph (Digraph)**: A graph where edges have a direction.
        
    * **Undirected Graph**: A graph where edges do not have a direction.
        
    * **Weighted Graph**: A graph where edges have weights representing cost, distance, or any metric.
        
    * **Unweighted Graph**: A graph where edges do not have weights.
        
    
    **Types of Graphs**:
    
    * **Adjacency Matrix**: A 2D array where a cell represents the presence or absence of an edge between vertices.
        
    * **Adjacency List**: An array of lists where each list represents the neighbors of a vertex.
        
    
    **Python Example of a Graph Using Adjacency List**:
    
    ```python
    class Graph:
        def __init__(self):
            self.graph = {}
    
        def add_edge(self, u, v):
            if u not in self.graph:
                self.graph[u] = []
            self.graph[u].append(v)
    
        def print_graph(self):
            for vertex in self.graph:
                print(f"{vertex} -> {', '.join(map(str, self.graph[vertex]))}")
    
    g = Graph()
    g.add_edge(0, 1)
    g.add_edge(0, 2)
    g.add_edge(1, 2)
    g.add_edge(2, 0)
    g.add_edge(2, 3)
    g.add_edge(3, 3)
    g.print_graph()
    # Output:
    # 0 -> 1, 2
    # 1 -> 2
    # 2 -> 0, 3
    # 3 -> 3
    ```
    

### Applications of Non-Linear Data Structures

1. **Trees**:
    
    * **Binary Search Trees**: Used in searching and sorting algorithms, such as in databases for indexing.
        
    * **Heaps**: Used in priority queues, graph algorithms like Dijkstra's algorithm, and in heap sort.
        
    * **Tries**: Used in dictionary implementations, spell checkers, and autocomplete features.
        
2. **Graphs**:
    
    * **Social Networks**: Representing relationships between users.
        
    * **Transport Networks**: Modeling routes and connections in transportation systems.
        
    * **Web Crawling**: Representing links between web pages.
        
    * **Dependency Graphs**: Managing project dependencies in build systems and package managers.
        

Understanding and efficiently utilizing non-linear data structures are crucial for solving complex problems and designing efficient algorithms in various domains.

### UseCase Of This Data Structure

* **Trees**:
    
    * Hierarchical data structure with a root and hierarchical relationships.
        
    * Useful in representing hierarchical data (file systems, organizational structures), implementing search algorithms (binary search trees), and balancing data (AVL trees, Red-Black trees).
        
* **Graphs**:
    
    * Non-linear data structure composed of nodes and edges.
        
    * Used in representing networks (social networks, transportation networks), routing algorithms (shortest path), and dependency management.
        

These data structures cater to various computational needs, offering different trade-offs in terms of efficiency, flexibility, and ease of implementation depending on the specific use case and requirements of the application.