🌲 Module 4: Trees (Hierarchical Data Structure)

Understand non-linear hierarchical tree structures, complete 14-term terminology dictionary, node pointers, and memory layout.

💡 1. What is a Tree?

A Tree is a non-linear, hierarchical data structure consisting of nodes connected by edges. Unlike linear structures (Arrays, Linked Lists, Stacks, Queues), trees represent parent-child relationships with a single Root node at the top.

🌲 Interactive Terminology Tree Inspector Canvas

Click Any Term Below to Highlight

👆 Click any of the 14 terminology cards below to dynamically highlight its nodes, paths & edges in the tree above!

📖 Complete Tree Terminology Dictionary

👑

Root Node

The topmost node in the tree hierarchy having no parent node.

👨‍👧

Parent Node

The immediate predecessor node that links down to a child node.

👶

Child Node

A node connected directly below a parent node.

👯

Siblings

Nodes that share the exact same parent node.

🍃

Leaf Node (External)

A terminal node that has 0 children (left=NULL, right=NULL).

🏛️

Internal Node

Any non-leaf node that has at least 1 child node.

👴

Ancestor

Any node along the path from the root node down to that node.

🧒

Descendant

Any node reachable in the subtree rooted below that node.

📐

Degree of Node / Tree

Number of children of a node. Max degree in binary trees is 2.

📏

Depth of Node

Number of edges on path from Root down to that node. Root depth = 0.

📐

Height of Tree / Node

Number of edges on longest path from node down to a leaf.

📊

Level

Level = Depth + 1. Root is at Level 1.

🔗

Edge

The directional link connecting parent node to child node.

🌲🌲

Forest

A set or collection of zero or more disjoint trees.

🌿 2. Binary Tree Basics & C Struct Definition

A Binary Tree is a tree structure where every node has at most 2 children, referred to as the left child and right child.

// C Struct Memory Layout for Binary Tree Node
struct Node {
    int data;           // 4 Bytes Data
    struct Node* left;  // 8 Bytes Left Pointer (Heap RAM)
    struct Node* right; // 8 Bytes Right Pointer (Heap RAM)
};                      // Total = 24 Bytes (with 8-byte pointer padding)

🔄 3. Tree Traversals Engine (DFS & BFS)

Tree traversal means visiting every node in a specific order. Select a traversal mode below to step through and highlight nodes on the tree:

🌲 Binary Search Tree (BST) Node Simulator

Perform Node Insertion, Search, Deletion (Leaf, 1 child, 2 children), Find Min, and Find Max.

Value:

Click ➕ Insert Node or 🔍 Search Node above to step manually.

Ready

⚡ GCC C Line Execution TrackerNo active variables

⚡ 5. Time Complexity, Balanced vs Unbalanced & Diameter

Operation	Balanced BST (AVL / Red-Black)	Unbalanced / Skewed BST	Space Complexity
Search	O(log N)	O(N)	`O(h)`
Insert	O(log N)	O(N)	`O(h)`
Delete	O(log N)	O(N)	`O(h)`
Traversals	O(N)	O(N)	`O(h)`

📏 Diameter of Binary Tree

The Diameter (or width) of a tree is defined as the length (number of edges) of the longest path between any two leaf nodes in the tree. It may or may not pass through the root!

💻 Essential C Programs & Problems Suite for Trees

Production-ready, compilable C implementations for university exams and coding interviews.

1. Complete Binary Search Tree (BST) in C

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

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

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

struct Node* insert(struct Node* root, int val) {
    if (root == NULL) return createNode(val);
    if (val < root->data) root->left = insert(root->left, val);
    else if (val > root->data) root->right = insert(root->right, val);
    return root;
}

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

int main() {
    struct Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    printf("Inorder BST: ");
    inorder(root);
    printf("\n");
    return 0;
}

2. Count Nodes, Leaf Nodes, Internal Nodes & Size

// Total Nodes Count / Size of Tree
int countNodes(struct Node* root) {
    if (root == NULL) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

// Count Leaf Nodes (External Nodes with 0 children)
int countLeafNodes(struct Node* root) {
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) return 1;
    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

// Count Internal Nodes (Non-leaf nodes with at least 1 child)
int countInternalNodes(struct Node* root) {
    if (root == NULL || (root->left == NULL && root->right == NULL)) return 0;
    return 1 + countInternalNodes(root->left) + countInternalNodes(root->right);
}

3. Sum of Nodes, Maximum & Minimum Element

// Calculate Sum of all node values
int sumNodes(struct Node* root) {
    if (root == NULL) return 0;
    return root->data + sumNodes(root->left) + sumNodes(root->right);
}

// Find Maximum Element in Binary Tree
int findMax(struct Node* root) {
    if (root == NULL) return -99999; // Minimum integer sentinel
    int res = root->data;
    int lmax = findMax(root->left);
    int rmax = findMax(root->right);
    if (lmax > res) res = lmax;
    if (rmax > res) res = rmax;
    return res;
}

// Find Minimum Element in Binary Tree
int findMin(struct Node* root) {
    if (root == NULL) return 99999; // Maximum integer sentinel
    int res = root->data;
    int lmin = findMin(root->left);
    int rmin = findMin(root->right);
    if (lmin < res) res = lmin;
    if (rmin < res) res = rmin;
    return res;
}

4. Height / Max Depth of Binary Tree

// Height of Tree (Longest path from root down to a leaf node)
int getHeight(struct Node* root) {
    if (root == NULL) return 0;
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

5. Mirror Tree (In-Place Left & Right Subtree Swapping)

// Convert a Binary Tree into its Mirror Image (Invert Binary Tree)
void mirror(struct Node* root) {
    if (root == NULL) return;
    
    // Recursively mirror left and right subtrees
    mirror(root->left);
    mirror(root->right);
    
    // Swap left and right pointers
    struct Node* temp = root->left;
    root->left = root->right;
    root->right = temp;
}

6. Identical Trees (Check Structural & Data Equality)

// Check if two Binary Trees t1 and t2 are identical
int isIdentical(struct Node* t1, struct Node* t2) {
    if (t1 == NULL && t2 == NULL) return 1; // Both empty -> Identical
    if (t1 == NULL || t2 == NULL) return 0; // One empty -> Not identical
    
    return (t1->data == t2->data) &&
           isIdentical(t1->left, t2->left) &&
           isIdentical(t1->right, t2->right);
}

7. Symmetric Tree (Check Mirror Reflection Around Root)

int isMirror(struct Node* t1, struct Node* t2) {
    if (t1 == NULL && t2 == NULL) return 1;
    if (t1 == NULL || t2 == NULL) return 0;
    return (t1->data == t2->data) &&
           isMirror(t1->left, t2->right) &&
           isMirror(t1->right, t2->left);
}

// Check if a Binary Tree is symmetric around its center root
int isSymmetric(struct Node* root) {
    if (root == NULL) return 1;
    return isMirror(root->left, root->right);
}