Introduction to Trees in C

What Is a Tree?

A Tree is a non-linear data structure consisting of nodes connected by edges.

• Top-most node is called Root
• Nodes under a parent are called Children
• Nodes with no children are Leaf Nodes
• Length of longest path from root → leaf is Height
• Each node stores data and links to children

Tree Structure (Diagram)

        A (Root)
       / \
      B   C
     / \   \
    D   E   F

Parent → Child Relationship

Why Are Trees Used?

• Fast searching and sorting (O(log n))
• Efficient hierarchical representation
• Used in compilers (syntax trees)
• Used in file systems (directory tree)
• Foundation of many algorithms & data structures

Important Tree Terminologies

• Node: Element in a tree
• Root: Top node
• Parent: Node above
• Child: Node below
• Leaf: No children
• Edge: Connection between nodes
• Height: Longest path to leaf
• Subtree: Tree inside a tree

Binary Tree

A Binary Tree is a special tree where each node can have at most two children:

    Binary Tree Node
    ----------------
      struct node {
          int data;
          struct node *left;
          struct node *right;
      };

• Used in searching (BST)
• Used in balancing (AVL, Red-Black Trees)
• Used in heaps

Binary Tree Node in C

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

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

struct node* createNode(int value){
    struct node *n = (struct node*)malloc(sizeof(struct node));
    n->data = value;
    n->left = NULL;
    n->right = NULL;
    return n;
}

Tree Traversal

Traversal means visiting all nodes in a fixed order:

• Inorder → Left, Root, Right
• Preorder → Root, Left, Right
• Postorder → Left, Right, Root

Traversal Example

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

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

struct node* create(int value){
    struct node *n = malloc(sizeof(struct node));
    n->data = value;
    n->left = n->right = NULL;
    return n;
}

void inorder(struct node *root){
    if(root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

Uses of Trees

• File Explorer (Folders ↔ Subfolders)
• Databases (B-Trees, B+ Trees)
• Compiler Syntax Trees
• Game AI (Decision Trees)
• Networking (Routing Trees)

Practice Questions

1. What is a tree? Explain with a diagram.
2. Define root, leaf, and height of a tree.
3. Difference between general tree and binary tree?
4. Explain inorder, preorder, and postorder traversal.
5. Write a C program to create a tree node.

Practice Task

Tree Examples (10 Examples)

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

/* Example 1 – Create root node */
struct node{ int data; struct node *left,*right; };
struct node* newNode(int x){
    struct node *n = malloc(sizeof(struct node));
    n->data=x; n->left=n->right=NULL; return n;
}
int main(){ struct node *root=newNode(5); printf("%d",root->data); }

/* Example 2 – Inorder Traversal */
void inorder(struct node *root){
    if(!root) return;
    inorder(root->left);
    printf("%d ",root->data);
    inorder(root->right);
}

/* Example 3 – Preorder Traversal */
void preorder(struct node *root){
    if(!root) return;
    printf("%d ",root->data);
    preorder(root->left);
    preorder(root->right);
}

/* Example 4 – Postorder Traversal */
void postorder(struct node *root){
    if(!root) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ",root->data);
}

/* Example 5 – Insert Left Child */
root->left = newNode(20);

/* Example 6 – Insert Right Child */
root->right = newNode(30);

/* Example 7 – Check if Leaf */
int isLeaf(struct node *n){ return (n->left==NULL && n->right==NULL); }

/* Example 8 – Count Nodes */
int count(struct node *root){
    if(!root) return 0;
    return 1 + count(root->left) + count(root->right);
}

/* Example 9 – Tree Height */
int height(struct node *root){
    if(!root) return 0;
    int L=height(root->left), R=height(root->right);
    return (L>R ? L : R) + 1;
}

/* Example 10 – Search in Tree */
int search(struct node *root,int key){
    if(!root) return 0;
    if(root->data==key) return 1;
    return search(root->left,key) || search(root->right,key);
}