Tree Data Structure in C (Basic Concepts with Examples)

This tutorial explains the Tree data structure in C, a hierarchical structure used for efficient data storage and retrieval. It covers basic concepts, terminology, types of trees, and simple implementation to strengthen problem-solving skills.

1. What is a Tree

  1. A tree is a hierarchical data structure consisting of nodes
  2. Each node contains data and pointers to child nodes
  3. The topmost node is called root
  4. Nodes with no children are called leaf nodes

Example Diagram:


1
/ \
2 3
/ \
4 5

2. Terminology

TermDescription
RootTop node of the tree
NodeBasic unit containing data
EdgeLink between two nodes
ParentNode with child nodes
ChildNode connected to parent
LeafNode with no children
SubtreeTree formed by a node and its descendants
HeightMaximum depth of the tree

3. Types of Trees

  1. Binary Tree: Each node has at most two children (left and right)
  2. Binary Search Tree (BST): Left child < parent < right child
  3. Full Binary Tree: Every node has 0 or 2 children
  4. Complete Binary Tree: All levels are filled except possibly last, left-aligned
  5. Perfect Binary Tree: All internal nodes have 2 children and all leaves are at same level

4. Simple Binary Tree Implementation in C


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

// Node structure
struct Node {
int data;
struct Node *left;
struct Node *right;
};

// Create new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}

// Pre-order traversal
void preorder(struct Node* root) {
if(root == NULL) return;
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}

int main() {
struct Node *root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);

printf("Preorder Traversal: ");
preorder(root);

return 0;
}

Output:


Preorder Traversal: 1 2 4 5 3

5. Key Points to Remember

  1. Trees are hierarchical, not linear
  2. Useful for searching, sorting, hierarchical data, expression parsing
  3. Binary Tree is basic form, BST is for efficient searching
  4. Traversals include Preorder, Inorder, Postorder
  5. Nodes can have children, parent, and leaves