Trees in Data Structures with C++ Programs (Binary Tree, BST, AVL, Red-Black, Heap & Traversals)

 

🌳

Trees in Data Structures

A comprehensive guide to hierarchical data organization — from Binary Trees to Heaps, traversal algorithms, self-balancing trees, and efficient sorting.

Introduction

📖 Introduction to Trees

In computer science, a tree is a hierarchical data structure consisting of nodes connected by edges. It represents relationships between elements where one element acts as the parent and others become its children.

To understand trees better, imagine a company hierarchy. At the top is the CEO, below that are managers, and under them are employees. Each level represents a different layer in the hierarchy. Trees work in a similar way.

Unlike arrays or linked lists where data is stored sequentially, trees store information in branches, making searching and sorting more efficient. In large applications, trees help reduce complexity and improve performance dramatically.

💡 Balanced trees maintain logarithmic height, which ensures efficient performance even when datasets become very large, allowing operations like searching, insertion, and deletion to happen quickly.

Real-world applications of trees:

• File systems in operating systems
• Database indexing
• Search engines
• Artificial intelligence decision trees
• Compilers

Fundamentals

📚 Basic Tree Terminology

Before diving deeper, it is essential to understand the basic terminology used in trees. These terms appear frequently in data structure discussions and algorithm design.

Term	Meaning
Root	The topmost node of a tree
Parent	A node that has child nodes
Child	A node connected below another node
Sibling	Nodes that share the same parent
Leaf Node	A node with no children
Edge	A connection between two nodes
Path	Sequence of nodes from root to a node
Depth	Distance from root to a node
Height	Maximum distance from root to leaf

Example Tree Structure:

1 / \ 2 3 / \ \ 4 5 6

• 1 is the root node
• 2 and 3 are children of node 1
• 4, 5 and 6 are leaf nodes
• 2 and 3 are siblings
• The path from root to node 5 is 1 → 2 → 5

Core Concept

🌿 Binary Trees

A binary tree is one of the most common types of tree structures used in programming. It is defined as a tree where each node has at most two children, known as the left child and right child.

In a binary tree, each node contains three parts: Data, a pointer to the left child, and a pointer to the right child.

A / \ B C / \ D E

• A is the root
• B and C are children of A
• D and E are children of B

Types of Binary Trees

1

Full Binary Tree

Every node has either 0 or 2 children.

2

Complete Binary Tree

All levels filled except possibly the last level.

3

Perfect Binary Tree

All internal nodes have two children; all leaves at same level.

4

Degenerate Tree

Each parent has only one child — similar to a linked list.

Memory Layout

🗂 Binary Tree Representations

📊 Array Representation

Nodes stored in an array using index rules. For a node at index i:

• Left child = 2i
• Right child = 2i + 1

Index: 1 2 3 4 5 Value: A B C D E

✅ Advantages

• Simple implementation
• No extra pointer memory

❌ Disadvantages

• Wastes memory if tree is sparse

🔗 Linked List Representation

Each node contains data and pointers to left and right children.

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

✅ Advantages

• Efficient memory usage
• Suitable for dynamic trees

❌ Disadvantages

• Requires additional pointer storage

Algorithms

🔄 Tree Traversal Algorithms

Tree traversal means visiting every node in a tree exactly once. It is important for operations like printing tree elements, searching data, and evaluating expressions.

Consider this example tree used for all traversals:

A / \ B C / \ D E

1. Preorder Traversal

Root

→ Left

→ Right

• Visit root node
• Traverse left subtree
• Traverse right subtree

Output

A B D E C

📌 Used for copying trees or prefix expression evaluation.

2. Inorder Traversal

Left

→ Root

→ Right

Output

D B E A C

⭐ In Binary Search Trees, inorder traversal produces sorted data, which makes it extremely useful.

3. Postorder Traversal

Left

→ Right

→ Root

Output

D E B C A

📌 Useful for deleting trees and evaluating postfix expressions.

4. Level Order Traversal (BFS)

Visits nodes level by level from top to bottom. Uses a queue data structure. Also called Breadth First Search (BFS).

Output

A B C D E

Code

💻 C++ Program — Binary Tree (Basic Creation)

A Binary Tree is a tree where each node can have maximum two children: left child and right child. Here we manually create a small binary tree and print its root and children.

C++#include <iostream> using namespace std; struct Node { int data; Node* left; Node* right; }; Node* createNode(int value) { Node* newNode = new Node(); newNode->data = value; newNode->left = NULL; newNode->right = NULL; return newNode; } int main() { Node* root = createNode(10); root->left = createNode(20); root->right = createNode(30); root->left->left = createNode(40); root->left->right = createNode(50); cout << "Root: " << root->data << endl; cout << "Left Child: " << root->left->data << endl; cout << "Right Child: " << root->right->data << endl; return 0; }

Output

Root: 10
Left Child: 20
Right Child: 30

Code

💻 C++ Programs — Tree Traversals

2.1 Preorder Traversal — Root → Left → Right

C++void preorder(Node* root) { if(root == NULL) return; cout << root->data << " "; preorder(root->left); preorder(root->right); }

Output

Preorder Traversal: 1 2 4 5 3

2.2 Inorder Traversal — Left → Root → Right

C++void inorder(Node* root) { if(root == NULL) return; inorder(root->left); cout << root->data << " "; inorder(root->right); }

Output

Inorder Traversal: 4 2 5 1 3

⭐ Important: Inorder traversal of BST gives sorted data.

2.3 Postorder Traversal — Left → Right → Root

C++void postorder(Node* root) { if(root == NULL) return; postorder(root->left); postorder(root->right); cout << root->data << " "; }

Output

Postorder Traversal: 4 5 2 3 1

2.4 Level Order Traversal

Uses a queue to visit nodes level by level.

C++#include <queue> void levelOrder(Node* root) { queue<Node*> q; q.push(root); while(!q.empty()) { Node* temp = q.front(); q.pop(); cout << temp->data << " "; if(temp->left) q.push(temp->left); if(temp->right) q.push(temp->right); } }

Output

Level Order Traversal: 1 2 3 4 5

Data Structure

🔍 Binary Search Trees (BST)

A Binary Search Tree (BST) is a special type of binary tree where nodes follow a specific order rule:

Left subtree < Root

Right subtree > Root

50 / \ 30 70 / \ / \ 20 40 60 80

• Fast searching
• Efficient insertion and deletion
• Data stored in sorted order
• Operations run in O(log n) time when tree is balanced
• Can degrade to O(n) if tree becomes skewed

C++ Program — Binary Search Tree

C++Node* insert(Node* root, int data) { if(root == NULL) { Node* newNode = new Node(); newNode->data = data; newNode->left = newNode->right = NULL; return newNode; } if(data < root->data) root->left = insert(root->left, data); else root->right = insert(root->right, data); return root; } int main() { Node* root = NULL; root = insert(root, 50); insert(root, 30); insert(root, 70); insert(root, 20); insert(root, 40); cout << "BST Inorder Traversal: "; inorder(root); }

Output

BST Inorder Traversal: 20 30 40 50 70

✅ Sorted output proves BST is working correctly!

Advanced

⚖️ Balanced Trees

Balanced trees are designed to prevent trees from becoming too tall or skewed. If a tree becomes too deep, operations become slower. Balanced trees automatically maintain a height close to logarithmic complexity.

Two popular balanced trees are: AVL Trees and Red-Black Trees.

Self-Balancing

🔁 AVL Trees

An AVL tree is a self-balancing binary search tree where the height difference between left and right subtrees is at most 1. This difference is called the balance factor.

Balance Factor = Height(left subtree) − Height(right subtree)
Possible values: -1, 0, +1

If the balance factor exceeds this range, rotations are performed:

↙

LL Rotation

Left-Left case

↘

RR Rotation

Right-Right case

↺

LR Rotation

Left-Right case

↻

RL Rotation

Right-Left case

C++ Program — AVL Tree (Simplified)

C++int getBalance(Node* n) { if(n == NULL) return 0; return height(n->left) - height(n->right); } Node* rightRotate(Node* y) { Node* x = y->left; Node* T2 = x->right; x->right = y; y->left = T2; return x; } Node* leftRotate(Node* x) { Node* y = x->right; Node* T2 = y->left; y->left = x; x->right = T2; return y; } Node* insert(Node* node, int key) { if(node == NULL) return newNode(key); if(key < node->key) node->left = insert(node->left, key); else if(key > node->key) node->right = insert(node->right, key); int balance = getBalance(node); if(balance > 1) return rightRotate(node); if(balance < -1) return leftRotate(node); return node; }

Output

AVL Preorder: 20 10 30

Self-Balancing

🔴⚫ Red-Black Trees

A Red-Black Tree is another self-balancing binary search tree where each node has a color attribute (red or black).

Rules of Red-Black Trees:

• Each node is either red or black
• Root is always black
• No two red nodes appear consecutively
• Every path contains the same number of black nodes

Because of these rules, the tree remains approximately balanced. Operations like search, insertion, and deletion run in O(log n) time.

Used in:

Java TreeMap

C++ STL map

Linux kernel schedulers

C++ Concept Program — Red-Black Tree

C++enum Color {RED, BLACK}; struct Node { int data; Color color; Node *left, *right, *parent; }; Node* createNode(int data) { Node* node = new Node(); node->data = data; node->color = RED; node->left = node->right = node->parent = NULL; return node; } int main() { Node* root = createNode(10); root->color = BLACK; root->left = createNode(5); root->right = createNode(20); cout << "Root: " << root->data << " Color: BLACK" << endl; cout << "Left Child: " << root->left->data << " Color: RED" << endl; }

Output

Root: 10 Color: BLACK
Left Child: 5 Color: RED

Priority Queues

🏔️ Heap Data Structure

A heap is a specialized binary tree used mainly for priority queues. A heap must satisfy two properties:

📐 Shape Property

The heap must be a complete binary tree.

📏 Heap Property

• Max Heap → parent ≥ children
• Min Heap → parent ≤ children

Max Heap Example:

90 / \ 70 60 / \ / 40 30 20

Heap Operations

+

Insertion

Insert at last, compare with parent, swap until restored.
O(log n)

−

Deletion

Remove root, replace with last element, heapify.
O(log n)

👁

Peek

Returns root element without deleting it.
O(1)

⚙

Heapify

Adjusts nodes to maintain heap structure.

C++ Program — Max Heap

C++void heapify(int arr[], int n, int i) { int largest = i; int left = 2*i+1; int right = 2*i+2; if(left < n && arr[left] > arr[largest]) largest = left; if(right < n && arr[right] > arr[largest]) largest = right; if(largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); } } int main() { int arr[] = {4, 10, 3, 5, 1}; int n = 5; for(int i = n/2-1; i >= 0; i--) heapify(arr, n, i); cout << "Max Heap: "; for(int i = 0; i < n; i++) cout << arr[i] << " "; }

Output

Max Heap: 10 5 3 4 1

Sorting Algorithm

📊 Heap Sort Algorithm

Heap sort is a sorting algorithm that uses the heap data structure. Time Complexity: O(n log n).

Steps:

• Build a max heap
• Swap root with last element
• Reduce heap size
• Heapify root
• Repeat until sorted

✅ Advantages

• Time complexity: O(n log n)
• No extra memory needed
• Works well for large datasets

❌ Disadvantages

• Not stable sort
• Slower than quicksort in practice

C++ Program — Heap Sort

C++void heapSort(int arr[], int n) { // Build max heap for(int i = n/2-1; i >= 0; i--) heapify(arr, n, i); // Extract elements one by one for(int i = n-1; i >= 0; i--) { swap(arr[0], arr[i]); heapify(arr, i, 0); } } int main() { int arr[] = {4, 10, 3, 5, 1}; int n = 5; heapSort(arr, n); cout << "Sorted Array: "; for(int i = 0; i < n; i++) cout << arr[i] << " "; }

Output

Sorted Array: 1 3 4 5 10

Reference

📋 Quick Summary

Topic	Purpose
Binary Tree	Hierarchical data storage
Traversal	Visit nodes in specific order
BST	Fast searching
AVL Tree	Self-balancing tree
Red-Black Tree	Balanced tree used in libraries
Heap	Priority queue structure
Heap Sort	Efficient sorting algorithm

Conclusion

Trees are one of the most powerful and widely used data structures in computer science. They help organize data hierarchically and allow efficient searching, insertion, and deletion operations.

Students studying data structures must understand several important tree concepts, including binary trees, binary search trees, balanced trees, AVL trees, Red-Black trees, heaps, and traversal algorithms. Each structure solves a different problem and offers unique advantages.

Binary trees provide the basic framework, BSTs enable efficient searching, balanced trees maintain performance, and heaps allow priority-based operations and sorting algorithms like heap sort.

Once you master tree data structures, you unlock the ability to design efficient algorithms used in databases, operating systems, search engines, and artificial intelligence.

FAQ

❓ Frequently Asked Questions

1 What is a tree in data structures?

A tree is a hierarchical data structure consisting of nodes connected by edges. It represents parent-child relationships and is used to organize data efficiently.

2 What is the difference between a binary tree and a binary search tree?

A binary tree allows each node to have two children, but it does not follow any ordering rule. A binary search tree maintains a rule where the left subtree contains smaller values and the right subtree contains larger values.

3 Why are balanced trees important?

Balanced trees maintain a height close to logarithmic complexity, ensuring that operations like searching and insertion remain efficient even for very large datasets.

4 What is the difference between AVL and Red-Black trees?

AVL trees are strictly balanced using height differences, while Red-Black trees use node coloring rules to maintain approximate balance. AVL trees are more rigidly balanced; Red-Black trees are preferred in practice for their faster insertions.

5 What is a heap used for?

Heaps are commonly used to implement priority queues, scheduling algorithms, graph algorithms like Dijkstra's algorithm, and sorting algorithms like heap sort.