Data Structure and Algorithm
Introduction to Tree Data Structure with Practical Examples
 Tree Data Structure
 Fundamental Tree Terminologies
 Types of Tree Data Structure
 Implementation of a Tree in C++
 Tree Traversal Methods:
 Applications of Tree Data Structures
 Run C Programming Online Compiler
Have you ever wondered how your computer neatly organizes all your files and folders? It’s not just random magic; there’s a clever system behind it called a tree data structure. Each file has its own unique path connecting it to others. This structure makes it super easy to find and manage your files, whether you’re looking for a document or a photo album. But the usefulness of tree data structures doesn’t stop there; they’re also essential in organizing things like database indexing, data compression and even in everyday tasks like navigating through menus on your phone.
¶Tree Data Structure
A tree data structure is a nonlinear, acyclic, hierarchical organization of data, consisting of nodes connected by edges. Unlike linear data structures, trees arrange data in a manner that mirrors natural hierarchies, facilitating rapid data retrieval through various tree traversal algorithms such as inorder, preorder, and postorder traversal.
Serving as the backbone of numerous sophisticated algorithms, the tree data structure and its variants, including the binary search tree, binary tree, and complete binary tree, play pivotal roles in a wide array of realworld applications. These applications span from database management to network algorithms like the minimum spanning tree (MST) and are indispensable in fields requiring hierarchical data representation.
¶Fundamental Tree Terminologies

Node:
A fundamental unit of a tree data structure that contains data. 
Edge:
The connection between two nodes in a tree. 
Level:
The level of a node represents the distance of the node from the root node, with the root node being at level 0. 
Subtree:
A subtree is a smaller tree structure that is formed by any node in the tree along with all of its descendants. 
Parent:
A parent node is a node that comes before another node in the tree structure and serves as the immediate predecessor of the node in question. 
Child:
A child node is a node that directly follows another node in the tree. These are the immediate successors of their respective parent nodes. 
Root Node
: At the very top of the tree hierarchy, there exists a special node called the root node. This node does not have any parent nodes and serves as the starting point for traversing the entire tree. 
Leaf Node:
Leaf nodes are nodes that do not have any child nodes. These nodes mark the end points of branches in the tree structure. 
Ancestor:
An ancestor of a node refers to any node that precedes it along the path from the root node to that specific node. 
Descendant:
A descendant is any node that can be reached by following a path from a particular node.
¶Types of Tree Data Structure
There are several types of tree data structures, each with its own characteristics and applications. Some common types include:

Binary Tree:
A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. This structure is widely used in computer science for various applications such as binary search trees and expression trees. 
Binary Search Tree (BST):
A binary search tree is a type of binary tree in which the nodes are arranged in a specific order. For any node in the tree, all nodes in its left subtree have values less than the node’s value, and all nodes in its right subtree have values greater than the node’s value. BSTs are efficient for searching, inserting, and deleting elements. 
AVL Tree:
An AVL tree is a selfbalancing binary search tree in which the heights of the two child subtrees of any node differ by at most one. This balancing ensures that the tree remains relatively balanced, leading to improved performance for search, insertion, and deletion operations. 
BTree:
A Btree is a balanced tree data structure that maintains sorted data and allows for efficient insertion, deletion, and search operations. Btrees are used in databases and file systems where large amounts of data need to be stored and accessed efficiently. 
RedBlack Tree:
A redblack tree is a type of binary search tree with additional properties that ensure it remains balanced. These properties include coloring nodes either red or black and enforcing rules that maintain the balance of the tree during insertion and deletion operations. Redblack trees are used in various applications, including implementing sets and maps in programming languages and databases. 
Trie:
A trie, also known as a prefix tree, is a tree data structure used for storing a dynamic set of keys where each node represents a common prefix of its descendants’ keys. Tries are commonly used in applications involving string manipulation and information retrieval, such as autocomplete features in text editors and search engines.
¶Implementation of a Tree in C++
#include <iostream>
#include <vector>
using namespace std;
// Function to add an edge between two nodes in the tree
void addEdge(vector<vector<int>>& tree, int parent, int child) {
tree[parent].push_back(child);
}
// Function to perform a depthfirst traversal of the tree
void dfs(const vector<vector<int>>& tree, int node) {
cout << node << " ";
for (int child : tree[node]) {
dfs(tree, child);
}
}
int main() {
// Define the tree using adjacency lists
vector<vector<int>> tree(6); // Assuming 6 nodes in the tree
// Add edges to connect the nodes
addEdge(tree, 0, 1);
addEdge(tree, 0, 2);
addEdge(tree, 1, 3);
addEdge(tree, 1, 4);
addEdge(tree, 2, 5);
// Perform depthfirst traversal starting from the root (node 0)
cout << "DepthFirst Traversal:" << endl;
dfs(tree, 0);
cout << endl;
return 0;
}
DepthFirst Traversal:
0 1 3 4 2 5
In the adjacency list representation:

Node Representation: Each node in the tree is represented by an index in the vector. This index corresponds to the node’s position in the vector. For example, if a node has an index
i
, its adjacency list is stored attree[i]
. 
Adjacency Lists: Each element of the vector (
tree[i]
) is itself a list or vector. This list contains the indices of nodes that are adjacent to the node represented by indexi
. In a tree, these adjacent nodes are typically the children of the node represented by indexi
.  Adding Edges: To add an edge between two nodes in the tree, you simply append the index of the child node to the adjacency list of the parent node.
 Traversal: Traversing the tree using adjacency lists is typically done recursively. You start at the root node and explore its adjacency list, visiting each adjacent node (child), and recursively exploring their adjacency lists. This representation is memoryefficient, especially for sparse trees where nodes have relatively few children. It also allows for efficient traversal and exploration of the tree structure.
¶Tree Traversal Methods:

Preorder Traversal:
This method explores the current node before its child nodes. It’s commonly employed for tasks like creating a copy of the tree or generating prefix expressions from an expression tree.
#include <iostream>
using namespace std;
// Definition of a binary tree node
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
// Function to perform preorder traversal
void preOrderTraversal(TreeNode* root) {
if (root == nullptr) return;
// Visit the current node
cout << root>data << " ";
// Traverse the left subtree
preOrderTraversal(root>left);
// Traverse the right subtree
preOrderTraversal(root>right);
}
int main() {
// Construct the tree
TreeNode* root = new TreeNode(1);
root>left = new TreeNode(2);
root>right = new TreeNode(3);
root>left>left = new TreeNode(4);
root>left>right = new TreeNode(5);
root>right>left = new TreeNode(6);
root>right>right = new TreeNode(7);
// Perform preorder traversal
cout << "Preorder traversal: ";
preOrderTraversal(root);
cout << endl;
// Clean up memory
delete root>left>left;
delete root>left>right;
delete root>left;
delete root>right>left;
delete root>right>right;
delete root>right;
delete root;
return 0;
}
Preorder traversal: 1 2 4 5 3 6 7

Inorder Traversal:
In this approach, all nodes in the left subtree are visited first, followed by the current node, and then all nodes in the right subtree. In binary search trees, this results in nodes being visited in ascending order, making it ideal for tasks such as sorting.
#include <iostream>
#include <vector>
using namespace std;
// Definition of a binary tree node
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
// Function to perform inorder traversal
void inOrderTraversal(TreeNode* root) {
if (root == nullptr) return;
// Traverse the left subtree
inOrderTraversal(root>left);
// Visit the current node
cout << root>data << " ";
// Traverse the right subtree
inOrderTraversal(root>right);
}
int main() {
// Construct the tree from the adjacency list
TreeNode* root = new TreeNode(1);
root>left = new TreeNode(2);
root>right = new TreeNode(3);
root>left>left = new TreeNode(4);
root>left>right = new TreeNode(5);
root>right>left = new TreeNode(6);
root>right>right = new TreeNode(7);
// Perform inorder traversal
cout << "Inorder traversal: ";
inOrderTraversal(root);
cout << endl;
// Clean up memory
delete root>left>left;
delete root>left>right;
delete root>left;
delete root>right>left;
delete root>right>right;
delete root>right;
delete root;
return 0;
}
Inorder traversal: 4 2 5 1 6 3 7

Postorder Traversal:
Nodes are visited only after all their descendants have been visited. This method is useful for operations like deleting the tree or performing garbage collection.
#include <iostream>
using namespace std;
// Definition of a binary tree node
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
// Function to perform postorder traversal
void postOrderTraversal(TreeNode* root) {
if (root == nullptr) return;
// Traverse the left subtree
postOrderTraversal(root>left);
// Traverse the right subtree
postOrderTraversal(root>right);
// Visit the current node
cout << root>data << " ";
}
int main() {
// Construct the tree
TreeNode* root = new TreeNode(1);
root>left = new TreeNode(2);
root>right = new TreeNode(3);
root>left>left = new TreeNode(4);
root>left>right = new TreeNode(5);
root>right>left = new TreeNode(6);
root>right>right = new TreeNode(7);
// Perform postorder traversal
cout << "Postorder traversal: ";
postOrderTraversal(root);
cout << endl;
// Clean up memory
delete root>left>left;
delete root>left>right;
delete root>left;
delete root>right>left;
delete root>right>right;
delete root>right;
delete root;
return 0;
}
Postorder traversal: 4 5 2 6 7 3 1

Level Order Traversal:
This BFS variant entails visiting all nodes at one depth level before moving to the next level. It employs a FIFO (FirstInFirstOut) queue to ensure that nodes are processed in the order they are encountered.
#include <iostream>
#include <queue>
using namespace std;
// Definition of a binary tree node
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
// Function to perform level order traversal
void levelOrderTraversal(TreeNode* root) {
if (root == nullptr) return;
// Create a queue for level order traversal
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* current = q.front();
q.pop();
// Visit the current node
cout << current>data << " ";
// Enqueue the left child if exists
if (current>left != nullptr) {
q.push(current>left);
}
// Enqueue the right child if exists
if (current>right != nullptr) {
q.push(current>right);
}
}
}
int main() {
// Construct the tree
TreeNode* root = new TreeNode(1);
root>left = new TreeNode(2);
root>right = new TreeNode(3);
root>left>left = new TreeNode(4);
root>left>right = new TreeNode(5);
root>right>left = new TreeNode(6);
root>right>right = new TreeNode(7);
// Perform level order traversal
cout << "Level order traversal: ";
levelOrderTraversal(root);
cout << endl;
// Clean up memory
delete root>left>left;
delete root>left>right;
delete root>left;
delete root>right>left;
delete root>right>right;
delete root>right;
delete root;
return 0;
}
Level order traversal: 1 2 3 4 5 6 7
¶Applications of Tree Data Structures
 File System Organization: Trees structure the directory hierarchy in computer file systems, allowing for organized and efficient file storage and retrieval
 Data Compression: Huffman coding uses tree structures to encode data, reducing the size of data files by assigning shorter codes to more frequently used characters
 Abstract Syntax Trees (AST): Compilers use ASTs to parse and convert source code into an intermediate, treebased representation, facilitating the subsequent stages of code generation and optimization.
 Parsing Mechanisms: In compilers and interpreters, parsing trees analyze grammatical structure, significantly aiding in the programming language translation process.
 Game Playing Algorithms: In AI, decision trees predict possible moves in games like chess, optimizing decisionmaking processes by evaluating potential future states.
 Networking Algorithms: Trees underpin algorithms for network routing and topology discovery, crucial for data packet management and pathfinding in network infrastructures.
¶Run C Programming Online Compiler
To make your learning more effective, exercise the coding examples in the text editor below.
SingleSource Shortest Paths Algorithm  Dijkstra's Algorithm
Introduction to Binary Search with Practical Examples
All Tutorials in this playlist
Popular Tutorials
Categories

Artificial Intelligence (AI)
11

Bash Scripting
1

Bootstrap CSS
0

C Programming
14

C#
0

ChatGPT
1

Code Editor
2

Computer Engineering
3

CSS
28

Data Structure and Algorithm
18

Design Pattern in PHP
2

Design Patterns  Clean Code
1

EBook
1

Git Commands
1

HTML
19

Interview Prepration
2

Java Programming
0

JavaScript
12

Laravel PHP Framework
37

Mysql
1

Node JS
1

Online Business
0

PHP
28

Programming
8

Python
12

React Js
19

React Native
1

Redux
2

Rust Programming
15

SEO  Search Engine Optimization
1

Tailwind CSS
1

Typescript
10

Uncategorized
0

Vue JS
1

Windows Operating system
1

Woocommerce
1

WordPress Development
2
Tags
 Artificial Intelligence (AI)
 Bash Scripting
 Business
 C
 C Programming
 Csharp programming
 C++
 Code Editor
 Computer Engineering
 CSS
 Data Structure and Algorithm
 Database
 Design pattern
 Express JS
 git
 Git Commands
 github
 HTML
 Java
 JavaScript
 Laravel
 Mathematics
 MongoDB
 Mysql
 Node JS
 PHP
 Programming
 Python
 React Js
 Redux
 Rust Programming Language
 SEO
 TypeScript
 Vue JS
 Windows terminal
 Woocommerce
 WordPress
 WordPress Plugin Development