Explore Courses
Liverpool Business SchoolLiverpool Business SchoolMBA by Liverpool Business School
  • 18 Months
Bestseller
Golden Gate UniversityGolden Gate UniversityMBA (Master of Business Administration)
  • 15 Months
Popular
O.P.Jindal Global UniversityO.P.Jindal Global UniversityMaster of Business Administration (MBA)
  • 12 Months
New
Birla Institute of Management Technology Birla Institute of Management Technology Post Graduate Diploma in Management (BIMTECH)
  • 24 Months
Liverpool John Moores UniversityLiverpool John Moores UniversityMS in Data Science
  • 18 Months
Popular
IIIT BangaloreIIIT BangalorePost Graduate Programme in Data Science & AI (Executive)
  • 12 Months
Bestseller
Golden Gate UniversityGolden Gate UniversityDBA in Emerging Technologies with concentration in Generative AI
  • 3 Years
upGradupGradData Science Bootcamp with AI
  • 6 Months
New
University of MarylandIIIT BangalorePost Graduate Certificate in Data Science & AI (Executive)
  • 8-8.5 Months
upGradupGradData Science Bootcamp with AI
  • 6 months
Popular
upGrad KnowledgeHutupGrad KnowledgeHutData Engineer Bootcamp
  • Self-Paced
upGradupGradCertificate Course in Business Analytics & Consulting in association with PwC India
  • 06 Months
OP Jindal Global UniversityOP Jindal Global UniversityMaster of Design in User Experience Design
  • 12 Months
Popular
WoolfWoolfMaster of Science in Computer Science
  • 18 Months
New
Jindal Global UniversityJindal Global UniversityMaster of Design in User Experience
  • 12 Months
New
Rushford, GenevaRushford Business SchoolDBA Doctorate in Technology (Computer Science)
  • 36 Months
IIIT BangaloreIIIT BangaloreCloud Computing and DevOps Program (Executive)
  • 8 Months
New
upGrad KnowledgeHutupGrad KnowledgeHutAWS Solutions Architect Certification
  • 32 Hours
upGradupGradFull Stack Software Development Bootcamp
  • 6 Months
Popular
upGradupGradUI/UX Bootcamp
  • 3 Months
upGradupGradCloud Computing Bootcamp
  • 7.5 Months
Golden Gate University Golden Gate University Doctor of Business Administration in Digital Leadership
  • 36 Months
New
Jindal Global UniversityJindal Global UniversityMaster of Design in User Experience
  • 12 Months
New
Golden Gate University Golden Gate University Doctor of Business Administration (DBA)
  • 36 Months
Bestseller
Ecole Supérieure de Gestion et Commerce International ParisEcole Supérieure de Gestion et Commerce International ParisDoctorate of Business Administration (DBA)
  • 36 Months
Rushford, GenevaRushford Business SchoolDoctorate of Business Administration (DBA)
  • 36 Months
KnowledgeHut upGradKnowledgeHut upGradSAFe® 6.0 Certified ScrumMaster (SSM) Training
  • Self-Paced
KnowledgeHut upGradKnowledgeHut upGradPMP® certification
  • Self-Paced
IIM KozhikodeIIM KozhikodeProfessional Certification in HR Management and Analytics
  • 6 Months
Bestseller
Duke CEDuke CEPost Graduate Certificate in Product Management
  • 4-8 Months
Bestseller
upGrad KnowledgeHutupGrad KnowledgeHutLeading SAFe® 6.0 Certification
  • 16 Hours
Popular
upGrad KnowledgeHutupGrad KnowledgeHutCertified ScrumMaster®(CSM) Training
  • 16 Hours
Bestseller
PwCupGrad CampusCertification Program in Financial Modelling & Analysis in association with PwC India
  • 4 Months
upGrad KnowledgeHutupGrad KnowledgeHutSAFe® 6.0 POPM Certification
  • 16 Hours
O.P.Jindal Global UniversityO.P.Jindal Global UniversityMaster of Science in Artificial Intelligence and Data Science
  • 12 Months
Bestseller
Liverpool John Moores University Liverpool John Moores University MS in Machine Learning & AI
  • 18 Months
Popular
Golden Gate UniversityGolden Gate UniversityDBA in Emerging Technologies with concentration in Generative AI
  • 3 Years
IIIT BangaloreIIIT BangaloreExecutive Post Graduate Programme in Machine Learning & AI
  • 13 Months
Bestseller
IIITBIIITBExecutive Program in Generative AI for Leaders
  • 4 Months
upGradupGradAdvanced Certificate Program in GenerativeAI
  • 4 Months
New
IIIT BangaloreIIIT BangalorePost Graduate Certificate in Machine Learning & Deep Learning (Executive)
  • 8 Months
Bestseller
Jindal Global UniversityJindal Global UniversityMaster of Design in User Experience
  • 12 Months
New
Liverpool Business SchoolLiverpool Business SchoolMBA with Marketing Concentration
  • 18 Months
Bestseller
Golden Gate UniversityGolden Gate UniversityMBA with Marketing Concentration
  • 15 Months
Popular
MICAMICAAdvanced Certificate in Digital Marketing and Communication
  • 6 Months
Bestseller
MICAMICAAdvanced Certificate in Brand Communication Management
  • 5 Months
Popular
upGradupGradDigital Marketing Accelerator Program
  • 05 Months
Jindal Global Law SchoolJindal Global Law SchoolLL.M. in Corporate & Financial Law
  • 12 Months
Bestseller
Jindal Global Law SchoolJindal Global Law SchoolLL.M. in AI and Emerging Technologies (Blended Learning Program)
  • 12 Months
Jindal Global Law SchoolJindal Global Law SchoolLL.M. in Intellectual Property & Technology Law
  • 12 Months
Jindal Global Law SchoolJindal Global Law SchoolLL.M. in Dispute Resolution
  • 12 Months
upGradupGradContract Law Certificate Program
  • Self paced
New
ESGCI, ParisESGCI, ParisDoctorate of Business Administration (DBA) from ESGCI, Paris
  • 36 Months
Golden Gate University Golden Gate University Doctor of Business Administration From Golden Gate University, San Francisco
  • 36 Months
Rushford Business SchoolRushford Business SchoolDoctor of Business Administration from Rushford Business School, Switzerland)
  • 36 Months
Edgewood CollegeEdgewood CollegeDoctorate of Business Administration from Edgewood College
  • 24 Months
Golden Gate UniversityGolden Gate UniversityDBA in Emerging Technologies with Concentration in Generative AI
  • 36 Months
Golden Gate University Golden Gate University DBA in Digital Leadership from Golden Gate University, San Francisco
  • 36 Months
Liverpool Business SchoolLiverpool Business SchoolMBA by Liverpool Business School
  • 18 Months
Bestseller
Golden Gate UniversityGolden Gate UniversityMBA (Master of Business Administration)
  • 15 Months
Popular
O.P.Jindal Global UniversityO.P.Jindal Global UniversityMaster of Business Administration (MBA)
  • 12 Months
New
Deakin Business School and Institute of Management Technology, GhaziabadDeakin Business School and IMT, GhaziabadMBA (Master of Business Administration)
  • 12 Months
Liverpool John Moores UniversityLiverpool John Moores UniversityMS in Data Science
  • 18 Months
Bestseller
O.P.Jindal Global UniversityO.P.Jindal Global UniversityMaster of Science in Artificial Intelligence and Data Science
  • 12 Months
Bestseller
IIIT BangaloreIIIT BangalorePost Graduate Programme in Data Science (Executive)
  • 12 Months
Bestseller
O.P.Jindal Global UniversityO.P.Jindal Global UniversityO.P.Jindal Global University
  • 12 Months
WoolfWoolfMaster of Science in Computer Science
  • 18 Months
New
Liverpool John Moores University Liverpool John Moores University MS in Machine Learning & AI
  • 18 Months
Popular
Golden Gate UniversityGolden Gate UniversityDBA in Emerging Technologies with concentration in Generative AI
  • 3 Years
Rushford, GenevaRushford Business SchoolDoctorate of Business Administration (AI/ML)
  • 36 Months
Ecole Supérieure de Gestion et Commerce International ParisEcole Supérieure de Gestion et Commerce International ParisDBA Specialisation in AI & ML
  • 36 Months
Golden Gate University Golden Gate University Doctor of Business Administration (DBA)
  • 36 Months
Bestseller
Ecole Supérieure de Gestion et Commerce International ParisEcole Supérieure de Gestion et Commerce International ParisDoctorate of Business Administration (DBA)
  • 36 Months
Rushford, GenevaRushford Business SchoolDoctorate of Business Administration (DBA)
  • 36 Months
Liverpool Business SchoolLiverpool Business SchoolMBA with Marketing Concentration
  • 18 Months
Bestseller
Golden Gate UniversityGolden Gate UniversityMBA with Marketing Concentration
  • 15 Months
Popular
Jindal Global Law SchoolJindal Global Law SchoolLL.M. in Corporate & Financial Law
  • 12 Months
Bestseller
Jindal Global Law SchoolJindal Global Law SchoolLL.M. in Intellectual Property & Technology Law
  • 12 Months
Jindal Global Law SchoolJindal Global Law SchoolLL.M. in Dispute Resolution
  • 12 Months
IIITBIIITBExecutive Program in Generative AI for Leaders
  • 4 Months
New
IIIT BangaloreIIIT BangaloreExecutive Post Graduate Programme in Machine Learning & AI
  • 13 Months
Bestseller
upGradupGradData Science Bootcamp with AI
  • 6 Months
New
upGradupGradAdvanced Certificate Program in GenerativeAI
  • 4 Months
New
KnowledgeHut upGradKnowledgeHut upGradSAFe® 6.0 Certified ScrumMaster (SSM) Training
  • Self-Paced
upGrad KnowledgeHutupGrad KnowledgeHutCertified ScrumMaster®(CSM) Training
  • 16 Hours
upGrad KnowledgeHutupGrad KnowledgeHutLeading SAFe® 6.0 Certification
  • 16 Hours
KnowledgeHut upGradKnowledgeHut upGradPMP® certification
  • Self-Paced
upGrad KnowledgeHutupGrad KnowledgeHutAWS Solutions Architect Certification
  • 32 Hours
upGrad KnowledgeHutupGrad KnowledgeHutAzure Administrator Certification (AZ-104)
  • 24 Hours
KnowledgeHut upGradKnowledgeHut upGradAWS Cloud Practioner Essentials Certification
  • 1 Week
KnowledgeHut upGradKnowledgeHut upGradAzure Data Engineering Training (DP-203)
  • 1 Week
MICAMICAAdvanced Certificate in Digital Marketing and Communication
  • 6 Months
Bestseller
MICAMICAAdvanced Certificate in Brand Communication Management
  • 5 Months
Popular
IIM KozhikodeIIM KozhikodeProfessional Certification in HR Management and Analytics
  • 6 Months
Bestseller
Duke CEDuke CEPost Graduate Certificate in Product Management
  • 4-8 Months
Bestseller
Loyola Institute of Business Administration (LIBA)Loyola Institute of Business Administration (LIBA)Executive PG Programme in Human Resource Management
  • 11 Months
Popular
Goa Institute of ManagementGoa Institute of ManagementExecutive PG Program in Healthcare Management
  • 11 Months
IMT GhaziabadIMT GhaziabadAdvanced General Management Program
  • 11 Months
Golden Gate UniversityGolden Gate UniversityProfessional Certificate in Global Business Management
  • 6-8 Months
upGradupGradContract Law Certificate Program
  • Self paced
New
IU, GermanyIU, GermanyMaster of Business Administration (90 ECTS)
  • 18 Months
Bestseller
IU, GermanyIU, GermanyMaster in International Management (120 ECTS)
  • 24 Months
Popular
IU, GermanyIU, GermanyB.Sc. Computer Science (180 ECTS)
  • 36 Months
Clark UniversityClark UniversityMaster of Business Administration
  • 23 Months
New
Golden Gate UniversityGolden Gate UniversityMaster of Business Administration
  • 20 Months
Clark University, USClark University, USMS in Project Management
  • 20 Months
New
Edgewood CollegeEdgewood CollegeMaster of Business Administration
  • 23 Months
The American Business SchoolThe American Business SchoolMBA with specialization
  • 23 Months
New
Aivancity ParisAivancity ParisMSc Artificial Intelligence Engineering
  • 24 Months
Aivancity ParisAivancity ParisMSc Data Engineering
  • 24 Months
The American Business SchoolThe American Business SchoolMBA with specialization
  • 23 Months
New
Aivancity ParisAivancity ParisMSc Artificial Intelligence Engineering
  • 24 Months
Aivancity ParisAivancity ParisMSc Data Engineering
  • 24 Months
upGradupGradData Science Bootcamp with AI
  • 6 Months
Popular
upGrad KnowledgeHutupGrad KnowledgeHutData Engineer Bootcamp
  • Self-Paced
upGradupGradFull Stack Software Development Bootcamp
  • 6 Months
Bestseller
KnowledgeHut upGradKnowledgeHut upGradBackend Development Bootcamp
  • Self-Paced
upGradupGradUI/UX Bootcamp
  • 3 Months
upGradupGradCloud Computing Bootcamp
  • 7.5 Months
PwCupGrad CampusCertification Program in Financial Modelling & Analysis in association with PwC India
  • 5 Months
upGrad KnowledgeHutupGrad KnowledgeHutSAFe® 6.0 POPM Certification
  • 16 Hours
upGradupGradDigital Marketing Accelerator Program
  • 05 Months
upGradupGradAdvanced Certificate Program in GenerativeAI
  • 4 Months
New
upGradupGradData Science Bootcamp with AI
  • 6 Months
Popular
upGradupGradFull Stack Software Development Bootcamp
  • 6 Months
Bestseller
upGradupGradUI/UX Bootcamp
  • 3 Months
PwCupGrad CampusCertification Program in Financial Modelling & Analysis in association with PwC India
  • 4 Months
upGradupGradCertificate Course in Business Analytics & Consulting in association with PwC India
  • 06 Months
upGradupGradDigital Marketing Accelerator Program
  • 05 Months

4 Types of Trees in Data Structures Explained: Properties & Applications

Updated on 12 November, 2024

62.79K+ views
22 min read

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(log⁡n)O(\log n)O(logn).

Types of Binary Trees

Binary trees can be divided into several types based on specific properties:

  1. Perfect Binary Tree:

    Every node has exactly two children, and all leaf nodes are at the same level.

  2. Full Binary Tree:

    Each parent node has either two or zero children.

  3. Complete Binary Tree:

    All levels are completely filled except possibly the last, which is filled from left to right.

  4. Degenerate (Pathological) Binary Tree:

    Every internal node has only one child, forming a structure similar to a linked list.

  5. 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

  • Decision 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(log⁡n)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

  1. Root Node (50):

    1. The first value inserted, 50, becomes the root of the tree. It is the highest point in the hierarchy, with no parent node.

    2. This root node serves as the reference point for the organization of all other nodes.

  2. Left Subtree:

    1. Values less than 50 are placed in the left subtree, maintaining the BST property.

    2. Node 30 is the left child of the root (50) and serves as the parent to nodes 20 and 40:

      1. 20: Placed in the left subtree of 30 since it is less than 30.

      2. 40: Placed in the right subtree of 30 because it is greater than 30 but still less than 50.

  3. Right Subtree:

    1. Values greater than or equal to 50 are placed in the right subtree, following the BST rules.

    2. Node 70 is the right child of the root (50) and is the parent of nodes 60 and 80:

      1. 60: Placed in the left subtree of 70 because it is less than 70 but greater than 50.

      2. 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(log⁡n)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

  1. 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.

  2. Rotation Functions:

    • rotateRight():

      Rotates the subtree to the right to reduce imbalance.

    • rotateLeft():

      Rotates the subtree to the left to reduce imbalance.

  3. 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.

  4. 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:

  1. 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.

  2. 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.

  3. 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

  1. 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.
  2. 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.
  3. 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!

A Stronger Profile and Exciting Opportunities Await—explore upGrad & IIIT-Bangalore’s Executive PG Programme in Software Development. Highly recommended for those looking to improve their programming career!

Transform your passion for data into a successful career with our top-rated Data Science courses, offering hands-on experience and industry-relevant skills.

Stay informed and inspired with our popular Data Science articles, featuring the latest trends, expert insights, and practical tips for aspiring data professionals.

Enhance your career by mastering top Data Science skills, from machine learning to data visualization, and stay ahead in the fast-evolving tech landscape.

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(log⁡n)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(log⁡n)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.