Tree in Data Structure

What is a Tree?

A tree is a non-linear data structure that stores data in a hierarchical form. It consists of nodes connected by edges. The topmost node of the tree is called the root node. Every node can have one or more child nodes. Trees help organize data in a structured and efficient manner. A family tree is a common real-life example of a tree structure.

Terminologies of a tree :-

1. Tree

A tree is a non-linear data structure that stores data in a hierarchical form. It consists of nodes connected by edges. The topmost node of the tree is called the root node. Every node can have one or more child nodes. Trees help organize data in a structured and efficient manner. A family tree is a common real-life example of a tree structure.

2. Subtree

A subtree is a smaller part of a tree that starts from a child node and includes all its descendants. Every child node in a tree can form its own subtree. Subtrees follow the same rules as the main tree. They help divide large trees into smaller sections. Subtrees are useful in searching and processing tree data. A family branch in a family tree is an example of a subtree.

3. Root Node

The root node is the first and topmost node in a tree. It is the starting point of the tree structure. Every tree must contain only one root node. All other nodes are connected directly or indirectly to the root. The root node has no parent node. In an organization chart, the CEO can be considered the root node.

4. Edge

An edge is the connection between two nodes in a tree. It represents the relationship between parent and child nodes. Edges help form the structure of the tree. A tree with N nodes contains N−1 edges. Without edges, nodes cannot communicate with each other. The line joining a parent and child in a family tree is an example of an edge.

5. Parent Node

A parent node is a node that has one or more child nodes. It is located above its child nodes in the hierarchy. A parent node helps create the structure of the tree. Every node except the root has a parent. A parent can have multiple children. In a family tree, a father or mother acts as a parent node.

6. Child Node

A child node is a node directly connected below a parent node. Every child node has a parent except the root node. Child nodes help form branches in a tree. A child node may also become a parent if it has children. Trees can have many child nodes at different levels. In a family tree, sons and daughters are child nodes.

7. Sibling Nodes

Sibling nodes are nodes that share the same parent node. They are located at the same level in the tree. Sibling nodes are related through a common parent. They do not have a parent-child relationship with each other. A parent may have two or more sibling nodes. Brothers and sisters in a family are examples of sibling nodes.

8. Leaf Node

A leaf node is a node that does not have any child nodes. It is usually found at the lowest level of a tree. Leaf nodes are also called terminal nodes. They represent the end points of tree branches. A tree can have multiple leaf nodes. The youngest members of a family tree are examples of leaf nodes.

9. Internal Node

An internal node is a node that has at least one child node. It is located between the root and leaf nodes. Internal nodes help connect different parts of the tree. The root node can also be an internal node if it has children. These nodes are important for traversal operations. Parents in a family tree are examples of internal nodes.

10. Degree of Node

The degree of a node is the number of child nodes connected to it. A node with no children has a degree of zero. Degree helps identify the branching factor of a node. The highest degree among all nodes is called the degree of the tree. Different nodes may have different degrees. A node having three children has a degree of three.

11. Level

The level of a node indicates its position in a tree. The root node is always at level zero. The children of the root are at level one. Their children are placed at level two and so on. Levels help organize nodes hierarchically. In a school hierarchy, principal, teachers, and students can represent different levels.

12. Height

The height of a tree is the number of edges in the longest path from the root node to a leaf node. It indicates how tall the tree is. Height is useful in measuring tree efficiency. A tree with only one node has a height of zero. Trees with smaller heights generally provide faster operations. The longest branch in a family tree determines its height.

13. Depth

Depth is the number of edges from the root node to a particular node. The root node has a depth of zero. Depth increases as we move down the tree. It helps determine the location of a node. Depth is important in searching and traversal. The distance between the CEO and an employee is similar to depth in a tree.

14. Path

A path is a sequence of nodes connected by edges. It shows the route from one node to another. A path may contain one or more edges. The length of a path depends on the number of edges present. Paths help in searching and traversal operations. The route from grandparent to grandchild in a family tree is a path. 

What is Ancestor and Descendants?

An ancestor is a node that appears above another node in a tree. A descendant is a node that appears below another node. The root node is an ancestor of all nodes in the tree. A node can have many descendants. These relationships help represent hierarchy. In a family tree, grandparents are ancestors and grandchildren are descendants. 

Types of tree :-

1. General Tree

A General Tree is a tree in which each node can have zero, one, or many child nodes. There is no fixed limit on the number of children a node can have. It is used to represent hierarchical relationships in a flexible way. General trees are commonly used in file systems and organization structures. They help store data in a parent-child relationship. A folder containing multiple subfolders is a simple example of a general tree.


2. Binary Tree

A Binary Tree is a non-linear data structure in which each node can have a maximum of two child nodes. These child nodes are known as the left child and right child. A node may have zero, one, or two children. Binary trees are widely used for searching and sorting operations. They help represent hierarchical data efficiently. A family structure where each parent has at most two children is an example of a binary tree.



Types of Binary tree :-

1. Full (Strict/Proper) Binary Tree

A Full Binary Tree is a binary tree in which every node has either zero or two children. No node is allowed to have only one child. The leaf nodes have no children, while internal nodes have exactly two children. This structure makes the tree well organized and easy to understand. It is also called a strict or proper binary tree. A family where every parent has exactly two children is an example of a full binary tree..



2. Complete Binary Tree

A Complete Binary Tree is a binary tree in which all levels are completely filled except possibly the last level. In the last level, all nodes must be placed as far left as possible. New nodes are inserted from left to right. This structure makes efficient use of memory space. Complete binary trees are commonly used in heap data structures. A classroom filled row by row from left to right is an example of a complete binary tree.



3. Perfect Binary Tree

A Perfect Binary Tree is a binary tree in which all internal nodes have exactly two children and all leaf nodes are at the same level. Every level of the tree is completely filled. This creates a balanced and symmetrical structure. Perfect binary trees provide efficient performance for many operations. Every perfect binary tree is also a full and complete binary tree. A perfectly balanced family hierarchy is an example of a perfect binary tree.



4. Degenerate Binary Tree

A Degenerate Binary Tree is a tree in which every parent node has only one child. The structure looks similar to a linked list. It may be left-skewed or right-skewed depending on the direction of the child nodes. Such trees are less efficient for searching operations. The height of the tree becomes very large compared to the number of nodes. A chain of people standing one behind another is an example of a degenerate binary tree.



5. Balanced Binary Tree

A Balanced Binary Tree is a tree in which the height difference between the left and right subtrees is at most one. This balance helps maintain efficient searching, insertion, and deletion operations. Balanced trees prevent the structure from becoming skewed. AVL trees and Red-Black trees are common examples of balanced binary trees. They provide better performance than unbalanced trees. A well-organized company hierarchy is an example of a balanced binary tree. 

    


Types of traversal in binary tree : - 

1. In-order Traversal (Left → Root → Right)

In this traversal, the left subtree is visited first, then the root node, and finally the right subtree. It is commonly used in Binary Search Trees because it displays data in sorted order. The traversal follows the sequence Left → Root → Right. This method visits every node exactly once. It is useful for retrieving data in ascending order. Example output: D → B → E → A → F → C → G.



2. Pre-order Traversal (Root → Left → Right)

In this traversal, the root node is visited first, followed by the left subtree and then the right subtree. It follows the sequence Root → Left → Right. This traversal is useful for creating a copy of a tree. It processes the parent node before its children. Every node is visited exactly once. Example output: A → B → D → E → C → F → G.



3. Post-order Traversal (Left → Right → Root)

In this traversal, the left subtree is visited first, then the right subtree, and finally the root node. It follows the sequence Left → Right → Root. This method is useful for deleting a tree because child nodes are processed before the parent node. Each node is visited only once. It is commonly used in expression trees. Example output: D → E → B → F → G → C → A. 



1. Implement Binary Tree creation using linked list in C
CODE : 

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *left, *right;
};

struct node* create();

int main()
{
    struct node *root;
    root = create();

    printf("Binary Tree Created Successfully");
    return 0;
}

struct node* create()
{
    struct node *temp;
    int data, choice;

    printf("\nPress 0 to exit");
    printf("\nPress 1 for new node");
    printf("\nEnter your choice: ");
    scanf("%d", &choice);

    if(choice == 0)
    {
        return NULL;
    }

    temp = (struct node*)malloc(sizeof(struct node));

    printf("Enter the data: ");
    scanf("%d", &data);

    temp->data = data;

    printf("Enter the left child of %d\n", data);
    temp->left = create();

    printf("Enter the right child of %d\n", data);
    temp->right = create();

    return temp;
}

Output  :