PROBLEM SOLVING - TREES IN C INTRODUCTION

Tree Basics in C

Tree Definition

A tree in C is a hierarchical data structure with nodes connected by edges. Key characteristics:

Root node - Topmost node with no parent
Leaf nodes - Nodes with no children
Binary trees - Each node has at most two children
BST - Binary Search Tree with ordered nodes

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

Tree Applications

Trees are fundamental in computer science with various applications:

Hierarchical data representation
File systems organization
Database indexing
Network routing algorithms
AI decision trees
Compilers (syntax trees)
Game development

Tree Initialization

Creating and initializing trees in C:

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

// Creating a simple tree
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);

Common Tree Traversals

Basic tree traversal techniques:

In-order - Left, Root, Right
Pre-order - Root, Left, Right
Post-order - Left, Right, Root
Level-order - Breadth-first using queue
Depth-first - Using recursion or stack

Accessing Tree Nodes

Traversing and accessing nodes in a tree:

// In-order traversal example
void inOrder(struct Node* node) {
    if (node == NULL) return;
    inOrder(node->left);
    printf("%d ", node->data);
    inOrder(node->right);
}

// Accessing root and children
int rootData = root->data;
int leftChild = root->left->data;
int rightChild = root->right->data;

Tree Characteristics and Terminology

Why Trees are Non-Linear

A tree is called non-linear because:

It doesn't store data sequentially
It forms a hierarchical, branching structure
Each node may connect to multiple children, unlike linear data structures

Structure	Type	Example
Array	Linear	A → B → C → D
Linked List	Linear	A → B → C → D → NULL
Tree	Non-Linear	A → {B, C}, B → {D, E}

Tree Terminology

Term	Meaning
Root node	Top node (only one per tree)
Edge/Branch	Link between two nodes
Parent node	A node with child
Child node	A descendent node to any parent node
Siblings nodes	Nodes with same parent
Leaf node	A node without any child (External/Terminal/End)
Ancestor node	Any predecessor node on path from root
Degree of node	Total number of children of that node
Degree of tree	Highest degree among all nodes
Internal node	A node with at least one child (including root)
Height of tree	Edges in longest path from root to leaf
Height of node x	Edges in longest path from node x to leaf (leaf height = 0)
Depth of node x	Edges from root to node x (root depth = 0)
Level	Steps from top (root level = 0)
Path	Sequence of nodes and edges between nodes
Sub tree	Child node with all its descendants
Forest	Collection of disjoint trees
Size of tree	Total number of nodes