- Blog Categories
- Software Development Projects and Ideas
- 12 Computer Science Project Ideas
- 28 Beginner Software Projects
- Top 10 Engineering Project Ideas
- Top 10 Easy Final Year Projects
- Top 10 Mini Projects for Engineers
- 25 Best Django Project Ideas
- Top 20 MERN Stack Project Ideas
- Top 12 Real Time Projects
- Top 6 Major CSE Projects
- 12 Robotics Projects for All Levels
- Java Programming Concepts
- Abstract Class in Java and Methods
- Constructor Overloading in Java
- StringBuffer vs StringBuilder
- Java Identifiers: Syntax & Examples
- Types of Variables in Java Explained
- Composition in Java: Examples
- Append in Java: Implementation
- Loose Coupling vs Tight Coupling
- Integrity Constraints in DBMS
- Different Types of Operators Explained
- Career and Interview Preparation in IT
- Top 14 IT Courses for Jobs
- Top 20 Highest Paying Languages
- 23 Top CS Interview Q&A
- Best IT Jobs without Coding
- Software Engineer Salary in India
- 44 Agile Methodology Interview Q&A
- 10 Software Engineering Challenges
- Top 15 Tech's Daily Life Impact
- 10 Best Backends for React
- Cloud Computing Reference Models
- Web Development and Security
- Find Installed NPM Version
- Install Specific NPM Package Version
- Make API Calls in Angular
- Install Bootstrap in Angular
- Use Axios in React: Guide
- StrictMode in React: Usage
- 75 Cyber Security Research Topics
- Top 7 Languages for Ethical Hacking
- Top 20 Docker Commands
- Advantages of OOP
- Data Science Projects and Applications
- 42 Python Project Ideas for Beginners
- 13 Data Science Project Ideas
- 13 Data Structure Project Ideas
- 12 Real-World Python Applications
- Python Banking Project
- Data Science Course Eligibility
- Association Rule Mining Overview
- Cluster Analysis in Data Mining
- Classification in Data Mining
- KDD Process in Data Mining
- Data Structures and Algorithms
- Binary Tree Types Explained
- Binary Search Algorithm
- Sorting in Data Structure
- Binary Tree in Data Structure
- Binary Tree vs Binary Search Tree
- Recursion in Data Structure
- Data Structure Search Methods: Explained
- Binary Tree Interview Q&A
- Linear vs Binary Search
- Priority Queue Overview
- Python Programming and Tools
- Top 30 Python Pattern Programs
- List vs Tuple
- Python Free Online Course
- Method Overriding in Python
- Top 21 Python Developer Skills
- Reverse a Number in Python
- Switch Case Functions in Python
- Info Retrieval System Overview
- Reverse a Number in Python
- Real-World Python Applications
- Data Science Careers and Comparisons
- Data Analyst Salary in India
- Data Scientist Salary in India
- Free Excel Certification Course
- Actuary Salary in India
- Data Analyst Interview Guide
- Pandas Interview Guide
- Tableau Filters Explained
- Data Mining Techniques Overview
- Data Analytics Lifecycle Phases
- Data Science Vs Analytics Comparison
- Artificial Intelligence and Machine Learning Projects
- Exciting IoT Project Ideas
- 16 Exciting AI Project Ideas
- 45+ Interesting ML Project Ideas
- Exciting Deep Learning Projects
- 12 Intriguing Linear Regression Projects
- 13 Neural Network Projects
- 5 Exciting Image Processing Projects
- Top 8 Thrilling AWS Projects
- 12 Engaging AI Projects in Python
- NLP Projects for Beginners
- Concepts and Algorithms in AIML
- Basic CNN Architecture Explained
- 6 Types of Regression Models
- Data Preprocessing Steps
- Bagging vs Boosting in ML
- Multinomial Naive Bayes Overview
- Gini Index for Decision Trees
- Bayesian Network Example
- Bayes Theorem Guide
- Top 10 Dimensionality Reduction Techniques
- Neural Network Step-by-Step Guide
- Technical Guides and Comparisons
- Make a Chatbot in Python
- Compute Square Roots in Python
- Permutation vs Combination
- Image Segmentation Techniques
- Generative AI vs Traditional AI
- AI vs Human Intelligence
- Random Forest vs Decision Tree
- Neural Network Overview
- Perceptron Learning Algorithm
- Selection Sort Algorithm
- Career and Practical Applications in AIML
- AI Salary in India Overview
- Biological Neural Network Basics
- Top 10 AI Challenges
- Production System in AI
- Top 8 Raspberry Pi Alternatives
- Top 8 Open Source Projects
- 14 Raspberry Pi Project Ideas
- 15 MATLAB Project Ideas
- Top 10 Python NLP Libraries
- Naive Bayes Explained
- Digital Marketing Projects and Strategies
- 10 Best Digital Marketing Projects
- 17 Fun Social Media Projects
- Top 6 SEO Project Ideas
- Digital Marketing Case Studies
- Coca-Cola Marketing Strategy
- Nestle Marketing Strategy Analysis
- Zomato Marketing Strategy
- Monetize Instagram Guide
- Become a Successful Instagram Influencer
- 8 Best Lead Generation Techniques
- Digital Marketing Careers and Salaries
- Digital Marketing Salary in India
- Top 10 Highest Paying Marketing Jobs
- Highest Paying Digital Marketing Jobs
- SEO Salary in India
- Brand Manager Salary in India
- Content Writer Salary Guide
- Digital Marketing Executive Roles
- Career in Digital Marketing Guide
- Future of Digital Marketing
- MBA in Digital Marketing Overview
- Digital Marketing Techniques and Channels
- 9 Types of Digital Marketing Channels
- Top 10 Benefits of Marketing Branding
- 100 Best YouTube Channel Ideas
- YouTube Earnings in India
- 7 Reasons to Study Digital Marketing
- Top 10 Digital Marketing Objectives
- 10 Best Digital Marketing Blogs
- Top 5 Industries Using Digital Marketing
- Growth of Digital Marketing in India
- Top Career Options in Marketing
- Interview Preparation and Skills
- 73 Google Analytics Interview Q&A
- 56 Social Media Marketing Q&A
- 78 Google AdWords Interview Q&A
- Top 133 SEO Interview Q&A
- 27+ Digital Marketing Q&A
- Digital Marketing Free Course
- Top 9 Skills for PPC Analysts
- Movies with Successful Social Media Campaigns
- Marketing Communication Steps
- Top 10 Reasons to Be an Affiliate Marketer
- Career Options and Paths
- Top 25 Highest Paying Jobs India
- Top 25 Highest Paying Jobs World
- Top 10 Highest Paid Commerce Job
- Career Options After 12th Arts
- Top 7 Commerce Courses Without Maths
- Top 7 Career Options After PCB
- Best Career Options for Commerce
- Career Options After 12th CS
- Top 10 Career Options After 10th
- 8 Best Career Options After BA
- Projects and Academic Pursuits
- 17 Exciting Final Year Projects
- Top 12 Commerce Project Topics
- Top 13 BCA Project Ideas
- Career Options After 12th Science
- Top 15 CS Jobs in India
- 12 Best Career Options After M.Com
- 9 Best Career Options After B.Sc
- 7 Best Career Options After BCA
- 22 Best Career Options After MCA
- 16 Top Career Options After CE
- Courses and Certifications
- 10 Best Job-Oriented Courses
- Best Online Computer Courses
- Top 15 Trending Online Courses
- Top 19 High Salary Certificate Courses
- 21 Best Programming Courses for Jobs
- What is SGPA? Convert to CGPA
- GPA to Percentage Calculator
- Highest Salary Engineering Stream
- 15 Top Career Options After Engineering
- 6 Top Career Options After BBA
- Job Market and Interview Preparation
- Why Should You Be Hired: 5 Answers
- Top 10 Future Career Options
- Top 15 Highest Paid IT Jobs India
- 5 Common Guesstimate Interview Q&A
- Average CEO Salary: Top Paid CEOs
- Career Options in Political Science
- Top 15 Highest Paying Non-IT Jobs
- Cover Letter Examples for Jobs
- Top 5 Highest Paying Freelance Jobs
- Top 10 Highest Paying Companies India
- Career Options and Paths After MBA
- 20 Best Careers After B.Com
- Career Options After MBA Marketing
- Top 14 Careers After MBA In HR
- Top 10 Highest Paying HR Jobs India
- How to Become an Investment Banker
- Career Options After MBA - High Paying
- Scope of MBA in Operations Management
- Best MBA for Working Professionals India
- MBA After BA - Is It Right For You?
- Best Online MBA Courses India
- MBA Project Ideas and Topics
- 11 Exciting MBA HR Project Ideas
- Top 15 MBA Project Ideas
- 18 Exciting MBA Marketing Projects
- MBA Project Ideas: Consumer Behavior
- What is Brand Management?
- What is Holistic Marketing?
- What is Green Marketing?
- Intro to Organizational Behavior Model
- Tech Skills Every MBA Should Learn
- Most Demanding Short Term Courses MBA
- MBA Salary, Resume, and Skills
- MBA Salary in India
- HR Salary in India
- Investment Banker Salary India
- MBA Resume Samples
- Sample SOP for MBA
- Sample SOP for Internship
- 7 Ways MBA Helps Your Career
- Must-have Skills in Sales Career
- 8 Skills MBA Helps You Improve
- Top 20+ SAP FICO Interview Q&A
- MBA Specializations and Comparative Guides
- Why MBA After B.Tech? 5 Reasons
- How to Answer 'Why MBA After Engineering?'
- Why MBA in Finance
- MBA After BSc: 10 Reasons
- Which MBA Specialization to choose?
- Top 10 MBA Specializations
- MBA vs Masters: Which to Choose?
- Benefits of MBA After CA
- 5 Steps to Management Consultant
- 37 Must-Read HR Interview Q&A
- Fundamentals and Theories of Management
- What is Management? Objectives & Functions
- Nature and Scope of Management
- Decision Making in Management
- Management Process: Definition & Functions
- Importance of Management
- What are Motivation Theories?
- Tools of Financial Statement Analysis
- Negotiation Skills: Definition & Benefits
- Career Development in HRM
- Top 20 Must-Have HRM Policies
- Project and Supply Chain Management
- Top 20 Project Management Case Studies
- 10 Innovative Supply Chain Projects
- Latest Management Project Topics
- 10 Project Management Project Ideas
- 6 Types of Supply Chain Models
- Top 10 Advantages of SCM
- Top 10 Supply Chain Books
- What is Project Description?
- Top 10 Project Management Companies
- Best Project Management Courses Online
- Salaries and Career Paths in Management
- Project Manager Salary in India
- Average Product Manager Salary India
- Supply Chain Management Salary India
- Salary After BBA in India
- PGDM Salary in India
- Top 7 Career Options in Management
- CSPO Certification Cost
- Why Choose Product Management?
- Product Management in Pharma
- Product Design in Operations Management
- Industry-Specific Management and Case Studies
- Amazon Business Case Study
- Service Delivery Manager Job
- Product Management Examples
- Product Management in Automobiles
- Product Management in Banking
- Sample SOP for Business Management
- Video Game Design Components
- Top 5 Business Courses India
- Free Management Online Course
- SCM Interview Q&A
- Fundamentals and Types of Law
- Acceptance in Contract Law
- Offer in Contract Law
- 9 Types of Evidence
- Types of Law in India
- Introduction to Contract Law
- Negotiable Instrument Act
- Corporate Tax Basics
- Intellectual Property Law
- Workmen Compensation Explained
- Lawyer vs Advocate Difference
- Law Education and Courses
- LLM Subjects & Syllabus
- Corporate Law Subjects
- LLM Course Duration
- Top 10 Online LLM Courses
- Online LLM Degree
- Step-by-Step Guide to Studying Law
- Top 5 Law Books to Read
- Why Legal Studies?
- Pursuing a Career in Law
- How to Become Lawyer in India
- Career Options and Salaries in Law
- Career Options in Law India
- Corporate Lawyer Salary India
- How To Become a Corporate Lawyer
- Career in Law: Starting, Salary
- Career Opportunities: Corporate Law
- Business Lawyer: Role & Salary Info
- Average Lawyer Salary India
- Top Career Options for Lawyers
- Types of Lawyers in India
- Steps to Become SC Lawyer in India
- Tutorials
- C Tutorials
- Recursion in C: Fibonacci Series
- Checking String Palindromes in C
- Prime Number Program in C
- Implementing Square Root in C
- Matrix Multiplication in C
- Understanding Double Data Type
- Factorial of a Number in C
- Structure of a C Program
- Building a Calculator Program in C
- Compiling C Programs on Linux
- Java Tutorials
- Handling String Input in Java
- Determining Even and Odd Numbers
- Prime Number Checker
- Sorting a String
- User-Defined Exceptions
- Understanding the Thread Life Cycle
- Swapping Two Numbers
- Using Final Classes
- Area of a Triangle
- Skills
- Software Engineering
- JavaScript
- Data Structure
- React.js
- Core Java
- Node.js
- Blockchain
- SQL
- Full stack development
- Devops
- NFT
- BigData
- Cyber Security
- Cloud Computing
- Database Design with MySQL
- Cryptocurrency
- Python
- Digital Marketings
- Advertising
- Influencer Marketing
- Search Engine Optimization
- Performance Marketing
- Search Engine Marketing
- Email Marketing
- Content Marketing
- Social Media Marketing
- Display Advertising
- Marketing Analytics
- Web Analytics
- Affiliate Marketing
- MBA
- MBA in Finance
- MBA in HR
- MBA in Marketing
- MBA in Business Analytics
- MBA in Operations Management
- MBA in International Business
- MBA in Information Technology
- MBA in Healthcare Management
- MBA In General Management
- MBA in Agriculture
- MBA in Supply Chain Management
- MBA in Entrepreneurship
- MBA in Project Management
- Management Program
- Consumer Behaviour
- Supply Chain Management
- Financial Analytics
- Introduction to Fintech
- Introduction to HR Analytics
- Fundamentals of Communication
- Art of Effective Communication
- Introduction to Research Methodology
- Mastering Sales Technique
- Business Communication
- Fundamentals of Journalism
- Economics Masterclass
- Free Courses
4 Types of Trees in Data Structures Explained: Properties & Applications
Updated on 12 November, 2024
62.79K+ views
• 22 min read
Table of Contents
How do computers manage to organize huge amounts of data so quickly? One big answer is the tree data structure. Like a tree in nature, this structure has a root that extends into branches and leaves. This setup makes it easy for computers to search and find data fast.
In simple terms, a data structure is a way to organize and store information. Data structures are the foundation of many computer programs and algorithms. They help create software that’s efficient and easy to work with. You’ll find data structures at work in fields like artificial intelligence and operating systems.
In this article, we’ll talk about “trees”, one of the most popular ways to organize data in a non-linear structure. We’ll go over the main types of tree structures, their unique features, and how they’re used in real life.
Check out our free data science courses to get an edge over the competition.
What is a Tree in Data Structure?
A tree is a data structure that organizes data in a hierarchical form. It consists of nodes connected by edges, which makes it different from linear data structures like arrays or linked lists. Each node contains data and may have child nodes, making it suitable for representing complex relationships. Trees are often seen as "upside-down," with the root at the top and branches growing downward.
Key Terms in Tree Data Structure
Term |
Definition |
Node |
Entity in the tree containing data and possibly child pointers |
Root |
Topmost node without a parent |
Parent |
A node directly connected above another node |
Child |
A node directly connected below another node |
Leaf |
Node with no children (bottom-most nodes) |
Edge |
Connection between two nodes |
Height |
Number of edges from the node to the farthest leaf |
Depth |
Number of edges from the root to a specific node |
Degree |
Number of branches or children of a node |
Subtree |
Any node and its descendants, forming a smaller tree within the main tree |
Forest |
A collection of disjoint trees |
Generation |
Nodes on the same level in the tree hierarchy |
Ancestor |
Any node that exists on the path from the root to a specific node |
Descendant |
Any node that is in the subtree of a specific node |
Sibling |
Nodes that share the same parent |
Levels |
The root node is at level 0, its children are at level 1, and so on |
Why Use Trees?
Trees make it easier to organize data that naturally forms a hierarchy, such as family relationships, organizational structures, or file systems. Here’s a quick example:
Look at the two diagrams below. They both represent family members. If you’re asked, “Who is the father of ‘E’?” or “What’s the relationship between ‘D’ and ‘E’?”, the second diagram makes it clear: ‘B’ is the father of ‘E’, and ‘D’ and ‘E’ are siblings. The first list, however, doesn’t give you any of that information.
This is the same with computers. When data is stored in a clear, hierarchical form, it’s faster and easier to find answers.
Now, let’s review the different types of tree data structures and see why they’re so useful.
Types of Trees in Data Structures
In data structures, trees come in various forms, each with specific properties and applications. Here, we'll discuss four primary types of trees:
1. Binary Tree
A binary tree is a tree data structure in which each node has a maximum of two children, typically referred to as the left child and the right child. The term "binary" means "two," indicating that each node can have zero, one, or two children. This structure is foundational for other complex tree types like Binary Search Trees (BST), AVL trees, and Red-Black Trees.
In a binary tree:
- The root node is the topmost node, and it has no parent.
- Every node contains pointers to its left and right children (if they exist).
- Leaf nodes (or terminal nodes) are nodes with no children, located at the bottom of the tree.
This structure makes binary trees effective for hierarchical data organization and retrieval. Binary trees are frequently used due to their balance between flexibility and simplicity.
Properties of a Binary Tree
Maximum nodes at level ‘L’:
At any level LLL, a binary tree can have up to 2L2^L2L nodes.
Minimum nodes at height HHH:
The minimum number of nodes in a binary tree of height HHH is H+1H + 1H+1.
Maximum nodes at height HHH:
At height HHH, a binary tree can have a maximum of 2H+1−12^{H+1} - 12H+1−1 nodes.
Total leaf nodes:
Equal to the total nodes with two children plus one.
Search complexity:
In a balanced binary tree, the search complexity is O(logn)O(\log n)O(logn).
Types of Binary Trees
Binary trees can be divided into several types based on specific properties:
Perfect Binary Tree:
Every node has exactly two children, and all leaf nodes are at the same level.
Full Binary Tree:
Each parent node has either two or zero children.
Complete Binary Tree:
All levels are completely filled except possibly the last, which is filled from left to right.
Degenerate (Pathological) Binary Tree:
Every internal node has only one child, forming a structure similar to a linked list.
Balanced Binary Tree:
The height difference between the left and right subtrees of every node is 0 or 1.
Consider doing our Python Bootcamp course from upGrad to upskill your career.
Example Applications of Binary Trees
Used in machine learning for classification and regression tasks.
Morse Code Representation:
Organized as a binary tree for efficient lookup of dots and dashes.
Binary Expression Trees:
Used to evaluate arithmetic expressions where operators are stored at internal nodes and operands at the leaf nodes.
Example Code: Basic Binary Tree in Python
Below is a Python example of a simple binary tree structure using classes. This example demonstrates how to create nodes and connect them as children.
python
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BinaryTree:
def __init__(self, root):
self.root = Node(root)
# Function to print the binary tree in a structured format
def print_tree(self, node, level=0, prefix="Root: "):
if node is not None:
print(" " * (level * 4) + prefix + str(node.data))
if node.left or node.right: # If the node has any children
if node.left:
self.print_tree(node.left, level + 1, "L--- ")
else:
print(" " * ((level + 1) * 4) + "L--- None")
if node.right:
self.print_tree(node.right, level + 1, "R--- ")
else:
print(" " * ((level + 1) * 4) + "R--- None")
# Building a binary tree
tree = BinaryTree(1)
tree.root.left = Node(2)
tree.root.right = Node(3)
tree.root.left.left = Node(4)
tree.root.left.right = Node(5)
# Printing the tree structure
print("Binary Tree Structure:")
tree.print_tree(tree.root)
In this code:
- We define a Node class, where each node has a data attribute and pointers (left and right) for its children.
- The BinaryTree class initializes a tree with a single root node.
- Additional nodes are manually added as left or right children of existing nodes, building a simple tree structure.
Visual Representation of the Example Binary Tree
Here's how the tree structure in the code would look:
markdown
1
/ \
2 3
/ \
4 5
Node 1 (Root):
Node 1 is the root of the tree, the topmost node with no parent. It has two children: node 2 (left child) and node 3 (right child).
- Left Pointer: Points to node 2.
- Right Pointer: Points to node 3.
Node 2 (Internal Node):
Node 2 is a child of node 1 and itself has two children: node 5 (left child) and node 6 (right child).
- Left Pointer: Points to node 5.
- Right Pointer: Points to node 6.
Node 3 (Leaf Node):
Node 3 is the right child of node 1. It has no children, so its left and right pointers are set to NULL, making it a leaf node.
Nodes 5 and 6 (Leaf Nodes):
Node 5 and node 6 are the children of node 2. Both are leaf nodes, meaning they have no children, so their left and right pointers are also set to NULL.
Code Output Explanation
To visualize or traverse the binary tree, we could use a simple traversal method. For example, performing an in-order traversal would visit nodes in the following order: 4, 2, 5, 1, 3.
python
# In-order traversal function
def in_order_traversal(node):
if node:
in_order_traversal(node.left) # Visit left subtree
print(node.data, end=" ") # Visit root node
in_order_traversal(node.right) # Visit right subtree
# Output the in-order traversal
print("In-order Traversal of the Tree:")
in_order_traversal(tree.root)
Expected Output:
4 2 5 1 3
In this traversal:
We first visit the left subtree, then the root node, and finally, the right subtree.
The output order (4, 2, 5, 1, 3) matches the in-order traversal sequence, showcasing how the binary tree is structured.
2. Binary Search Tree (BST)
A Binary Search Tree (BST) is a type of ordered binary tree designed for efficient data storage, retrieval, and searching. In a BST, each node’s left child contains values smaller than the node itself, while the right child contains values greater than or equal to the node. This ordering enables fast search, insertion, and deletion operations, making BSTs popular for applications where sorted data management is needed.
In essence, the BST structure allows for a divide-and-conquer approach to searching, where each decision (left or right) narrows down the possible locations of a target value, resulting in a search time complexity of O(logn)O(\log n)O(logn) for balanced trees.
Properties of a Binary Search Tree:
Left Subtree Rule: All nodes in the left subtree of a node have values smaller than the node’s value.
Right Subtree Rule: All nodes in the right subtree have values greater than or equal to the node’s value.
Recursive Structure: The left and right subtrees of each node are also binary search trees, following the same ordering rules.
Example Applications of Binary Search Trees:
Sorted Data Storage:
BSTs efficiently store data in a sorted manner, allowing quick insertion, search, and deletion.
Frequency Counters:
Useful for counting and storing elements in a sorted way, such as counting occurrences of words or items.
Game Guessing:
Ideal for guessing games where the process involves narrowing down a range of possibilities (e.g., "Guess the Number" games).
Code Example: Implementing a Binary Search Tree in Java
Here’s a simple Java implementation of a Binary Search Tree with basic insertion and search methods:
java
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
class BinarySearchTree {
Node root;
// Insert a new node with a given key
void insert(int data) {
root = insertRec(root, data);
}
// Recursive insert function
Node insertRec(Node root, int data) {
// If the tree is empty, create a new node
if (root == null) {
root = new Node(data);
return root;
}
// Recursively insert data into left or right subtree
if (data < root.data) {
root.left = insertRec(root.left, data);
} else if (data >= root.data) {
root.right = insertRec(root.right, data);
}
return root;
}
// Search for a key in the BST
boolean search(int key) {
return searchRec(root, key);
}
// Recursive search function
boolean searchRec(Node root, int key) {
// Base case: root is null or key is at root
if (root == null || root.data == key) {
return root != null;
}
// Key is less than root’s data
if (key < root.data) {
return searchRec(root.left, key);
}
// Key is greater than root’s data
return searchRec(root.right, key);
}
}
// Example usage
public class Main {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
// Insert nodes
bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);
bst.insert(60);
bst.insert(80);
// Search for a value
System.out.println("Is 40 in the BST? " + bst.search(40)); // Output: true
System.out.println("Is 90 in the BST? " + bst.search(90)); // Output: false
}
}
Explanation of the Code:
Node Class:
Defines the structure of a single node in the BST, with data, left, and right attributes.
BinarySearchTree Class:
Contains methods for inserting and searching nodes.
Insert Method:
The insert method adds a new node in the appropriate location by recursively comparing values.
Search Method:
The search method checks if a value exists in the BST by recursively traversing left or right based on comparisons.
Main Class:
Demonstrates how to create a BST, insert nodes, and perform searches.
Visual Representation of the Example BST
After inserting the values in the code example, the BST structure will look like this:
markdown
50
/ \
30 70
/ \ / \
20 40 60 80
Root Node (50):
The first value inserted, 50, becomes the root of the tree. It is the highest point in the hierarchy, with no parent node.
This root node serves as the reference point for the organization of all other nodes.
Left Subtree:
Values less than 50 are placed in the left subtree, maintaining the BST property.
Node 30 is the left child of the root (50) and serves as the parent to nodes 20 and 40:
20: Placed in the left subtree of 30 since it is less than 30.
40: Placed in the right subtree of 30 because it is greater than 30 but still less than 50.
Right Subtree:
Values greater than or equal to 50 are placed in the right subtree, following the BST rules.
Node 70 is the right child of the root (50) and is the parent of nodes 60 and 80:
60: Placed in the left subtree of 70 because it is less than 70 but greater than 50.
80: Placed in the right subtree of 70 as it is greater than both 70 and 50.
Must read: Excel online course free!
Code Output Explanation
When running the code:
bst.search(40) returns true because 40 is in the tree.
bst.search(90) returns false because 90 is not in the tree.
3. AVL Tree
An AVL Tree is a self-balancing variant of a Binary Search Tree (BST) named after its inventors, Adelson-Velsky and Landis. In an AVL tree, the height difference (or balance factor) between the left and right subtrees of any node is kept to a maximum of one. This balancing ensures that the tree remains efficient for search, insert, and delete operations, with a time complexity of O(logn)O(\log n)O(logn).
The AVL tree is unique as it was the first dynamically balanced tree structure, meaning it automatically adjusts itself to maintain balance through rotations whenever nodes are inserted or deleted. This balance keeps operations fast, especially in cases of frequent data manipulation.
Properties of an AVL Tree
Balance Factor:
The difference in height between the left and right subtrees of a node.
Calculated as
Balance Factor = Height of Left Subtree – Height of Right Subtree
Balance Factor Values:
The balance factor for each node can be -1, 0, or +1.
-1: Right subtree is one level higher than the left subtree.
0: Left and right subtrees are of equal height.
+1: Left subtree is one level higher than the right subtree.
Height Control with Rotations:
If an imbalance occurs (balance factor becomes outside the range -1 to 1), rotations (single or double) are performed to restore balance.
Applications of AVL Trees
In-Memory Databases:
AVL trees efficiently organize data in-memory for fast access.
Set and Dictionary Operations:
Useful in applications requiring frequent insertions, deletions, and lookups, as they maintain sorted data in a balanced form.
Code Example: AVL Tree Insertion with Rotations (C++)
Here's a C++ implementation of an AVL Tree with insertion and rotation methods to maintain balance.
cpp
#include <iostream>
using namespace std;
// Node class for AVL Tree
class Node {
public:
int data;
Node* left;
Node* right;
int height;
Node(int value) {
data = value;
left = right = nullptr;
height = 1;
}
};
// Helper function to get the height of a node
int getHeight(Node* node) {
return (node == nullptr) ? 0 : node->height;
}
// Helper function to get the balance factor of a node
int getBalanceFactor(Node* node) {
return (node == nullptr) ? 0 : getHeight(node->left) - getHeight(node->right);
}
// Rotate right
Node* rotateRight(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
return x;
}
// Rotate left
Node* rotateLeft(Node* x) {
Node* y = x->right;
Node* T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
return y;
}
// Insert function with balancing
Node* insert(Node* node, int key) {
// Perform standard BST insertion
if (node == nullptr)
return new Node(key);
if (key < node->data)
node->left = insert(node->left, key);
else if (key > node->data)
node->right = insert(node->right, key);
else // Duplicate keys not allowed
return node;
// Update height of this ancestor node
node->height = 1 + max(getHeight(node->left), getHeight(node->right));
// Get balance factor to check if this node is unbalanced
int balance = getBalanceFactor(node);
// Left Left Case
if (balance > 1 && key < node->left->data)
return rotateRight(node);
// Right Right Case
if (balance < -1 && key > node->right->data)
return rotateLeft(node);
// Left Right Case
if (balance > 1 && key > node->left->data) {
node->left = rotateLeft(node->left);
return rotateRight(node);
}
// Right Left Case
if (balance < -1 && key < node->right->data) {
node->right = rotateRight(node->right);
return rotateLeft(node);
}
return node; // Return the unchanged node pointer
}
// In-order traversal
void inOrder(Node* root) {
if (root != nullptr) {
inOrder(root->left);
cout << root->data << " ";
inOrder(root->right);
}
}
// Main function to demonstrate AVL Tree
int main() {
Node* root = nullptr;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
cout << "In-order traversal of the AVL tree is: ";
inOrder(root);
cout << endl;
return 0;
}
Must read: Data structures and algorithm free!
Explanation of Code
Node Class:
Each node contains data, pointers to left and right children, and height to keep track of the node’s level in the tree.
Rotation Functions:
rotateRight():
Rotates the subtree to the right to reduce imbalance.
rotateLeft():
Rotates the subtree to the left to reduce imbalance.
Insertion with Balancing:
The insert function inserts nodes as in a regular BST.
After insertion, it checks the balance factor to determine if rotations are needed to balance the tree.
In-order Traversal:
inOrder() function displays the AVL tree in sorted order to confirm the structure.
Visual Representation
After inserting nodes (10, 20, 30, 40, 50, 25) in the above order, the AVL Tree structure will balance itself to maintain efficiency:
markdown
30
/ \
20 40
/ \ \
10 25 50
Explanation of Rotations:
Inserting 10, 20, and 30:
Initially, the nodes 10 and 20 are inserted without any need for rotation.
However, upon inserting 30, the tree becomes unbalanced, with 10 as the root and a left-heavy structure.
To restore balance, a left rotation is applied at node 10, rotating the tree around node 20. This moves 20 to the root, with 10 as its left child and 30 as its right child.
Inserting 40 and 50:
Inserting 40 causes no imbalance, as it becomes the right child of 30.
When 50 is inserted as the right child of 40, the tree becomes right-heavy (since node 30 now has a balance factor greater than 1).
To rebalance, a right rotation is performed at node 30, making 40 the new root for that subtree.
Inserting 25:
Inserting 25 into the left subtree of 30 introduces a left-right imbalance.
To address this, a left rotation is first applied at 20, bringing 25 up as the right child of 20.
Then, a right rotation is performed at 30, which repositions 30 as the new root and maintains balance in the AVL Tree.
Code Output
The in-order traversal of the AVL tree will display the elements in sorted order:
swift
In-order traversal of the AVL tree
10 20 25 30 40 50
upGrad’s Exclusive Data Science Webinar for you –
ODE Thought Leadership Presentation
4. B-Tree
A B-Tree is a self-balancing search tree that generalizes the Binary Search Tree (BST). Unlike BSTs, each node in a B-Tree can contain multiple keys and have multiple children, making B-Trees highly efficient for handling large datasets. B-Trees are particularly popular in database indexing and file systems because they maintain balance and reduce tree height, optimizing access times even for disk-based storage.
In B-Trees:
- Nodes contain multiple keys, allowing for multi-way branching.
- The structure ensures that all leaf nodes are at the same depth, which maintains balance across the tree.
Properties of B-Trees
Order (m):
Defines the maximum number of children each node can have. A B-Tree of order m can have at most m children per node.
Minimum Children:
Every node (except the root) has at least m/2 children.
Root Node:
The root must have at least two children if it is not a leaf.
Keys per Node:
Each internal node can hold up to m-1 keys, which divide the node’s children.
Leaf Nodes:
All leaf nodes are at the same level, ensuring that the tree is balanced.
Multi-Level Indexing:
B-Trees use multi-level indexing, allowing quick access across large datasets with fewer disk reads.
Applications of B-Trees
Database Indexing:
B-Trees organize data in databases for efficient access, even with large data sets.
File Systems:
Used to manage files and directories in an optimized hierarchical structure, allowing fast data retrieval.
Multilevel Indexing:
B-Trees store keys to improve search speeds across vast datasets, making them ideal for applications requiring frequent lookups.
Code Example: B-Tree Insertion in Java
Below is a Java implementation demonstrating B-Tree insertion, focusing on managing multiple keys and ensuring balance.
java
class BTreeNode {
int[] keys; // Array to store keys
int degree; // Minimum degree (defines the range for number of children)
BTreeNode[] children; // Array of child pointers
int numKeys; // Current number of keys
boolean isLeaf; // Is true when the node is a leaf
// Constructor
public BTreeNode(int degree, boolean isLeaf) {
this.degree = degree;
this.isLeaf = isLeaf;
this.keys = new int[2 * degree - 1]; // Maximum keys a node can hold
this.children = new BTreeNode[2 * degree]; // Maximum children a node can have
this.numKeys = 0;
}
// Insert a new key in the subtree rooted with this node
public void insertNonFull(int key) {
int i = numKeys - 1;
// If this node is a leaf, insert key directly
if (isLeaf) {
while (i >= 0 && keys[i] > key) {
keys[i + 1] = keys[i];
i--;
}
keys[i + 1] = key;
numKeys++;
} else { // Node is not a leaf
while (i >= 0 && keys[i] > key) {
i--;
}
i++;
if (children[i].numKeys == 2 * degree - 1) {
splitChild(i, children[i]);
if (keys[i] < key) {
i++;
}
}
children[i].insertNonFull(key);
}
}
// Split the child node at the given index
public void splitChild(int i, BTreeNode y) {
BTreeNode z = new BTreeNode(y.degree, y.isLeaf);
z.numKeys = degree - 1;
for (int j = 0; j < degree - 1; j++) {
z.keys[j] = y.keys[j + degree];
}
if (!y.isLeaf) {
for (int j = 0; j < degree; j++) {
z.children[j] = y.children[j + degree];
}
}
y.numKeys = degree - 1;
for (int j = numKeys; j >= i + 1; j--) {
children[j + 1] = children[j];
}
children[i + 1] = z;
for (int j = numKeys - 1; j >= i; j--) {
keys[j + 1] = keys[j];
}
keys[i] = y.keys[degree - 1];
numKeys++;
}
}
class BTree {
BTreeNode root;
int degree;
public BTree(int degree) {
this.root = null;
this.degree = degree;
}
// Function to insert a new key in this B-Tree
public void insert(int key) {
if (root == null) {
root = new BTreeNode(degree, true);
root.keys[0] = key;
root.numKeys = 1;
} else {
if (root.numKeys == 2 * degree - 1) {
BTreeNode s = new BTreeNode(degree, false);
s.children[0] = root;
s.splitChild(0, root);
int i = 0;
if (s.keys[0] < key) {
i++;
}
s.children[i].insertNonFull(key);
root = s;
} else {
root.insertNonFull(key);
}
}
}
// Simple method to print the tree structure (in-order traversal)
public void print() {
if (root != null) {
print(root);
}
}
private void print(BTreeNode node) {
int i;
for (i = 0; i < node.numKeys; i++) {
if (!node.isLeaf) {
print(node.children[i]);
}
System.out.print(node.keys[i] + " ");
}
if (!node.isLeaf) {
print(node.children[i]);
}
}
}
// Main class to demonstrate the B-Tree
public class Main {
public static void main(String[] args) {
BTree btree = new BTree(3); // B-Tree of order 3
// Insert keys
btree.insert(10);
btree.insert(20);
btree.insert(5);
btree.insert(6);
btree.insert(12);
btree.insert(30);
btree.insert(7);
btree.insert(17);
System.out.println("B-Tree in-order traversal:");
btree.print(); // Expected Output: 5 6 7 10 12 17 20 30
}
}
Explanation of the Code
BTreeNode Class:
Represents a single node in the B-Tree.
- Stores keys, children, and a flag isLeaf to identify if the node is a leaf.
- insertNonFull method handles inserting a key in a non-full node.
- splitChild method splits a child node if it is full, helping maintain the B-Tree's properties.
BTree Class:
Manages the overall B-Tree structure.
- insert method handles root cases and calls insertNonFull for other nodes.
- print method performs an in-order traversal to display the tree.
Main Class:
Demonstrates how to create a B-Tree of order 3, insert keys, and display the tree structure.
Expected Output
The in-order traversal of the B-Tree after inserting the values will look like this:
css
B-Tree in-order traversal:
5 6 7 10 12 17 20 30
Applications of Tree Data Structures
Tree data structures are practical and widely used across different fields. Their hierarchy makes them ideal for organizing information in a way that's easy to access and understand. Here are some common uses:
Application |
How Trees Are Used |
File System Organization |
Trees organize files and folders on computers. Each folder can hold other folders and files, creating a clear path that helps us find files quickly. This structure lets users easily navigate through directories by following a logical “tree” path. |
Webpage Layout (HTML DOM) |
The layout of a webpage is structured as a tree. In HTML, each element (like a header, paragraph, or image) is a “node” in a tree, and nested elements are child nodes. This tree structure allows easy access and changes to webpage elements, enabling updates to content on the page. |
Database Indexing |
Trees, especially B-Trees and B+ Trees, help organize data in databases, making it faster to search and retrieve information. With large amounts of data, these trees keep data organized so that finding, adding, or deleting entries is efficient and manageable. |
Expression Evaluation |
Trees are used to evaluate mathematical or logical expressions. Binary Expression Trees store operators (like +, -, *) as parent nodes, while numbers or variables are leaf nodes. This makes it easy to evaluate expressions in the right order by following the tree structure. |
Routing Algorithms |
Trees help optimize routes in networks. Shortest Path Trees and Spanning Trees find the best paths for data to travel, reducing delays and improving network efficiency. These trees are useful in managing internet connections and ensuring data flows smoothly across the network. |
Kickstart Your Data Science Career with upGrad
Fast-Track Your Journey in Data Science!
- Learn essential skills for a successful career: data structures, machine learning, and practical algorithms.
Top Data Science Roles in Demand
- Job Titles: Data Scientist, Machine Learning Engineer, AI Specialist
- High-Demand Industries: Finance, Healthcare, Technology, E-commerce
Competitive Salary Outlook
- Entry-Level: $85K–$95K
- Mid-Level: $100K–$130K
- Senior-Level: $140K+
Skills You’ll Master with upGrad
- Foundational: Tree Structures, Data Analysis, Algorithms
- Advanced: Machine Learning, AI, Predictive Modeling
Why upGrad?
- Hands-On Learning: Real-world projects
- Expert Guidance: Mentorship from industry experts
- Global Credentials: Certifications from top universities
CTA: Ready to excel in data science? Enroll with upGrad today!
Transform your passion for data into a successful career with our top-rated Data Science courses, offering hands-on experience and industry-relevant skills.
Explore our Popular Data Science Courses
Stay informed and inspired with our popular Data Science articles, featuring the latest trends, expert insights, and practical tips for aspiring data professionals.
Read our popular Data Science Articles
Enhance your career by mastering top Data Science skills, from machine learning to data visualization, and stay ahead in the fast-evolving tech landscape.
Top Data Science Skills to Learn to upskill
SL. No | Top Data Science Skills to Learn | |
1 |
Data Analysis Online Courses | Inferential Statistics Online Courses |
2 |
Hypothesis Testing Online Courses | Logistic Regression Online Courses |
3 |
Linear Regression Courses | Linear Algebra for Analysis Online Courses |
Frequently Asked Questions (FAQs)
1. What’s the difference between a binary tree and a binary search tree?
A binary tree is a general structure where each node has at most two children. In contrast, a binary search tree (BST) follows specific ordering rules: all left descendants have values less than the node, and all right descendants have values greater than or equal to the node. This ordering allows BSTs to be efficient for searching and sorting data.
2. Why are AVL trees considered balanced trees?
AVL trees are called balanced trees because they automatically adjust their structure to ensure that the height difference (or balance factor) between the left and right subtrees of every node is no more than one. This balancing maintains efficient search, insertion, and deletion times.
3. How do B-trees differ from binary trees in terms of structure?
In a binary tree, each node can have up to two children. However, B-trees allow each node to have multiple children and keys. This structure makes B-trees ideal for managing large datasets and keeping trees shallow, which improves efficiency, especially in disk-based storage.
4. What are some real-life applications of binary search trees?
Binary search trees are used in applications requiring fast lookups and ordered data, such as maintaining ordered lists in databases, implementing sets and maps, and managing sorted collections for search algorithms.
5. How do trees improve search efficiency compared to linear data structures?
Trees improve search efficiency by organizing data hierarchically. Instead of searching elements one by one (as in lists or arrays), trees allow for quick navigation through levels, cutting down search time, especially in balanced trees like BSTs and AVL trees, which can operate in O(logn)O(\log n)O(logn) time.
6. Why are tree structures used in databases?
Tree structures, especially B-trees and B+ trees, are commonly used in databases to organize and index data. They keep data balanced and allow for efficient search, insertion, and deletion. This structure ensures that databases can handle large volumes of data while providing fast access to records.
7. How does a B-tree support multilevel indexing?
A B-tree supports multilevel indexing by storing multiple keys per node and allowing nodes to have multiple children. This structure reduces the tree's height and minimizes the number of disk accesses required for search operations, making it highly efficient for handling large datasets in databases.
8. What are the key benefits of self-balancing trees?
Self-balancing trees, such as AVL and Red-Black trees, ensure that operations like search, insert, and delete remain efficient by keeping the tree balanced. This balance prevents the tree from becoming too skewed, maintaining O(logn)O(\log n)O(logn) performance for all major operations.
9. Can a binary tree have more than two children?
No, in a binary tree, each node is limited to at most two children (left and right). Trees that allow more than two children per node, such as B-trees and general m-ary trees, follow different structures.
10. What are the advantages of AVL trees in in-memory sorting?
AVL trees are efficient for in-memory sorting because they maintain balance after each insertion. This balance keeps access times fast, making AVL trees ideal for situations where data is frequently updated and needs to remain sorted.
11. What’s the difference between complete and perfect binary trees?
In a perfect binary tree, every level is fully filled, and all leaf nodes are at the same depth. In a complete binary tree, all levels except possibly the last are fully filled, and nodes at the last level are as far left as possible. Perfect binary trees are a subset of complete binary trees, with stricter requirements.