Module 18: Trees

Learning Objectives

By the end of this module, you will be able to:

Understand tree data structures and terminology.
Learn Binary Trees, Binary Search Trees (BST), AVL Trees, Heaps, and Tries.
Perform tree traversals including Preorder, Inorder, Postorder, and Level Order.
Calculate the height and diameter of a tree.
Find the Lowest Common Ancestor (LCA).
Solve common tree-based interview problems.

Introduction

A Tree is a hierarchical, non-linear data structure used to organize data efficiently.

Unlike arrays and linked lists, trees represent parent-child relationships, making them ideal for hierarchical information.

Trees are widely used in:

File Systems
Database Indexing
Search Engines
Compiler Design
Artificial Intelligence
Routing Algorithms
Expression Trees
Operating Systems

What is a Tree?

A Tree consists of nodes connected by edges.

Example

text
1           10
2         /    \
3       20      30
4      /  \    /  \
5    40   50  60  70

Tree Terminology

Term	Description
Root	Topmost node
Parent	Node having children
Child	Node connected below another node
Leaf	Node with no children
Edge	Connection between two nodes
Height	Longest path from root to leaf
Depth	Distance from root to a node
Subtree	Tree inside another tree

Tree Node Structure

c
1#include <stdio.h>
2#include <stdlib.h>
3
4struct Node
5{
6    int data;
7    struct Node *left;
8    struct Node *right;
9};

Creating a Node

c
1struct Node* createNode(int value)
2{
3    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
4
5    newNode->data = value;
6    newNode->left = NULL;
7    newNode->right = NULL;
8
9    return newNode;
10}

Binary Tree

A Binary Tree is a tree where each node has at most two children.

Example

text
1          10
2        /    \
3      20      30
4     /  \
5   40   50

Properties

Maximum two children
Left child
Right child

Applications

Expression Trees
Decision Trees
Parsing
Huffman Coding

Binary Search Tree (BST)

A Binary Search Tree is a Binary Tree with an additional property.

Rule

text
1Left Subtree < Root < Right Subtree

Example

text
1          50
2        /    \
3      30      70
4     /  \    /  \
5   20   40  60  80

Advantages

Fast Searching
Fast Insertion
Fast Deletion

Average Time Complexity

Operation	Complexity
Search	O(log n)
Insert	O(log n)
Delete	O(log n)

Worst Case

text
1O(n)

BST Insertion

c
1struct Node* insert(struct Node *root, int value)
2{
3    if(root == NULL)
4        return createNode(value);
5
6    if(value < root->data)
7        root->left = insert(root->left, value);
8    else
9        root->right = insert(root->right, value);
10
11    return root;
12}

AVL Tree

An AVL Tree is a self-balancing Binary Search Tree.

Balance Factor

text
1Balance Factor = Height(Left) − Height(Right)

Allowed Values

text
1-1
2
30
4
51

If the balance factor becomes outside this range, rotations are performed.

AVL Rotations

There are four balancing cases:

Left Left (LL)
Right Right (RR)
Left Right (LR)
Right Left (RL)

Example

Before Rotation

After Right Rotation

Advantages

Guaranteed O(log n) search
Balanced tree
Better performance than an unbalanced BST

Applications

Databases
Search Systems
Memory Management

Heap

A Heap is a complete binary tree.

Two Types

Max Heap
Min Heap

Max Heap

Parent node is greater than its children.

Example

text
1        90
2      /    \
3    70      50
4   /  \
5 20   30

Min Heap

Parent node is smaller than its children.

Example

text
1        10
2      /    \
3    20      30
4   /  \
5 40   50

Applications

Priority Queue
Heap Sort
Scheduling
Dijkstra's Algorithm

Time Complexity

Operation	Complexity
Insert	O(log n)
Delete	O(log n)
Peek	O(1)

Trie

A Trie is a tree used for storing strings efficiently.

Example

Words

text
1cat
2
3car
4
5can

Trie

text
1          Root
2            |
3            c
4            |
5            a
6         /  |  \
7        t   r   n

Applications

Auto Complete
Spell Checker
Dictionary
Search Suggestions
IP Routing

Advantages

Fast prefix searching
Efficient dictionary lookup

Tree Traversals

Tree traversal means visiting every node exactly once.

There are four common traversal techniques.

Preorder Traversal

Order

text
1Root
2
3Left
4
5Right

Example

text
1        10
2      /    \
3     20     30

Traversal

text
110 20 30

Program

c
1void preorder(struct Node *root)
2{
3    if(root == NULL)
4        return;
5
6    printf("%d ", root->data);
7
8    preorder(root->left);
9    preorder(root->right);
10}

Time Complexity

text
1O(n)

Inorder Traversal

Order

text
1Left
2
3Root
4
5Right

Example

text
1        20
2      /    \
3    10      30

Output

text
110 20 30

For a BST, inorder traversal always returns elements in sorted order.

Program

c
1void inorder(struct Node *root)
2{
3    if(root == NULL)
4        return;
5
6    inorder(root->left);
7
8    printf("%d ", root->data);
9
10    inorder(root->right);
11}

Postorder Traversal

Order

text
1Left
2
3Right
4
5Root

Example

text
110 30 20

Program

c
1void postorder(struct Node *root)
2{
3    if(root == NULL)
4        return;
5
6    postorder(root->left);
7
8    postorder(root->right);
9
10    printf("%d ", root->data);
11}

Level Order Traversal

Visits nodes level by level.

Example

text
1Tree
2
3        10
4      /    \
5    20      30
6   /  \
7 40   50

Traversal

Level Order uses a Queue internally.

Time Complexity

text
1O(n)

Comparison of Traversals

Traversal	Order
Preorder	Root → Left → Right
Inorder	Left → Root → Right
Postorder	Left → Right → Root
Level Order	Level by Level

Practice Project 1: Tree Height

Height is the longest path from root to leaf.

Example

Height

text
13

Program

c
1int height(struct Node *root)
2{
3    if(root == NULL)
4        return 0;
5
6    int left = height(root->left);
7    int right = height(root->right);
8
9    return (left > right ? left : right) + 1;
10}

Time Complexity

text
1O(n)

Practice Project 2: Tree Diameter

The diameter is the length of the longest path between any two nodes.

Example

text
1        1
2       / \
3      2   3
4     /
5    4

Diameter

text
14 → 2 → 1 → 3

Simple Recursive Program

c
1int diameter(struct Node *root)
2{
3    if(root == NULL)
4        return 0;
5
6    int leftHeight = height(root->left);
7    int rightHeight = height(root->right);
8
9    int leftDiameter = diameter(root->left);
10    int rightDiameter = diameter(root->right);
11
12    int current = leftHeight + rightHeight + 1;
13
14    if(current > leftDiameter && current > rightDiameter)
15        return current;
16
17    return leftDiameter > rightDiameter ? leftDiameter : rightDiameter;
18}

Time Complexity

text
1O(n²)

Optimization: The diameter can be computed in O(n) by calculating the height and diameter together during a single traversal.

Practice Project 3: Lowest Common Ancestor (LCA)

The Lowest Common Ancestor (LCA) is the deepest node that is an ancestor of two given nodes.

Example

text
1          10
2        /    \
3      20      30
4     /  \
5   40   50

LCA

text
1LCA(40,50) = 20

Program

c
1struct Node* LCA(struct Node *root, int n1, int n2)
2{
3    if(root == NULL)
4        return NULL;
5
6    if(root->data == n1 || root->data == n2)
7        return root;
8
9    struct Node *left = LCA(root->left, n1, n2);
10    struct Node *right = LCA(root->right, n1, n2);
11
12    if(left && right)
13        return root;
14
15    return left ? left : right;
16}

Time Complexity

text
1O(n)

Real-World Applications of Trees

File System

text
1Root
2
3├── Documents
4
5├── Downloads
6
7└── Pictures

Database Indexing

Balanced trees such as AVL Trees and B-Trees are used for fast searching.

Search Engines

Trie structures provide fast word suggestions and autocomplete.

Compiler Design

Expression Trees are used to parse and evaluate expressions.

Networking

Routing tables use tree-based structures for efficient lookup.

Common Interview Questions

Difference between Binary Tree and BST.
Implement BST insertion.
Find the height of a tree.
Find the diameter of a tree.
Find the Lowest Common Ancestor.
Perform all four tree traversals.
Explain AVL Tree rotations.
Difference between Heap and BST.
Implement a Trie.
Validate whether a Binary Tree is a BST.

Common Mistakes to Avoid

Confusing a Binary Tree with a Binary Search Tree.
Forgetting the BST ordering rule (Left < Root < Right).
Not checking for NULL pointers during recursive traversal.
Assuming an unbalanced BST always provides O(log n) operations.
Miscalculating tree height by ignoring the base case.
Forgetting that Inorder Traversal returns sorted values only for a BST.

Best Practices

Use recursion for cleaner implementations of tree traversals.
Prefer balanced trees such as AVL Trees when frequent insertions and searches are required.
Use Heaps for priority-based processing rather than searching.
Use Tries for efficient prefix searches and autocomplete features.
Handle NULL nodes safely in all recursive functions.
Analyze the time and space complexity of recursive tree algorithms before optimizing.

Module Summary

In this module, you learned:

What trees are and how they represent hierarchical data.
The concepts of Binary Trees, Binary Search Trees (BSTs), AVL Trees, Heaps, and Tries.
How to perform Preorder, Inorder, Postorder, and Level Order traversals.
How to calculate the height and diameter of a tree.
How to find the Lowest Common Ancestor (LCA) of two nodes.
Real-world applications of trees in file systems, databases, search engines, and networking.

After completing this module, you'll be ready to learn Graphs, where you'll study graph representations, Breadth-First Search (BFS), Depth-First Search (DFS), shortest path algorithms, minimum spanning trees, topological sorting, and graph-based interview problems.