by Jasleen Chhabra | Updated on 24 August 2024

Trees are a widely used data structure that emulate a hierarchical tree structure with a set of connected nodes. Each node in a tree has a parent node and zero or more child nodes, making this structure ideal for representing hierarchical data.

Key Concepts of Trees

1. Root: The top node of the tree, which has no parent.
2. Node: An element in the tree that contains data.
3. Edge: The link between two nodes.
4. Leaf: A node with no children.
5. Parent: A node that has one or more child nodes.
6. Child: A node that has a parent node.
7. Subtree: A tree consisting of a node and its descendants.
8. Height: The length of the longest path from the root to a leaf.
9. Depth: The length of the path from the root to a node.

Types of Trees

1. Binary Tree: Each node has at most two children, referred to as the left child and the right child.
2. Binary Search Tree (BST): A binary tree where the left child contains only nodes with values less than the parent node and the right child contains only nodes with values greater than the parent node.
3. AVL Tree: A self-balancing binary search tree where the difference between the heights of left and right subtrees cannot be more than one for all nodes.
4. Red-Black Tree: A self-balancing binary search tree where nodes are colored red or black to ensure the tree remains balanced.
5. B-Tree: A self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.
6. Heap: A specialized tree-based data structure that satisfies the heap property (max-heap or min-heap).

Basic Operations on Trees

1. Insertion: Adding a node to the tree.
2. Deletion: Removing a node from the tree.
3. Traversal: Visiting all the nodes in the tree.
4. Searching: Finding a node with a specific value.

Tree Traversal Methods

1. In-order Traversal (LNR): Visit the left subtree, then the node, and finally the right subtree.
2. Pre-order Traversal (NLR): Visit the node, then the left subtree, and finally the right subtree.
3. Post-order Traversal (LRN): Visit the left subtree, then the right subtree, and finally the node.
4. Level-order Traversal: Visit nodes level by level starting from the root.

Algorithms for Basic Operations

Insertion in a Binary Search Tree (BST)

Algorithm:

1. Start from the root.
2. Compare the value to be inserted with the value of the current node.
3. If the value is less than the current node, go to the left subtree; if greater, go to the right subtree.
4. Repeat the process until an appropriate position is found.
5. Insert the new node at the position.

C++ Implementation:

struct Node {

    int data;

    Node* left;

    Node* right;

    Node(int value) : data(value), left(nullptr), right(nullptr) {}

};

 

Node* insert(Node* root, int key) {

    if (root == nullptr) {

        return new Node(key);

    }

    if (key < root->data) {

        root->left = insert(root->left, key);

    } else {

        root->right = insert(root->right, key);

    }

    return root;

}

---

Deletion in a Binary Search Tree (BST)

Algorithm:

1. Find the node to be deleted.
2. If the node is a leaf, simply remove it.
3. If the node has one child, replace the node with its child.
4. If the node has two children, find the inorder successor (smallest in the right subtree), copy its value to the node, and delete the inorder successor.

C++ Implementation:

Node* findMin(Node* root) {

    while (root->left != nullptr) {

        root = root->left;

    }

    return root;

}

 

Node* deleteNode(Node* root, int key) {

    if (root == nullptr) return root;

    if (key < root->data) {

        root->left = deleteNode(root->left, key);

    } else if (key > root->data) {

        root->right = deleteNode(root->right, key);

    } else {

        if (root->left == nullptr) {

            Node* temp = root->right;

            delete root;

            return temp;

        } else if (root->right == nullptr) {

            Node* temp = root->left;

            delete root;

            return temp;

        }

        Node* temp = findMin(root->right);

        root->data = temp->data;

        root->right = deleteNode(root->right, temp->data);

    }

    return root;

}

---

In-order Traversal

Algorithm:

1. Recursively visit the left subtree.
2. Visit the node.
3. Recursively visit the right subtree.

C++ Implementation:

void inOrderTraversal(Node* root) {

    if (root == nullptr) return;

    inOrderTraversal(root->left);

    std::cout << root->data << " ";

    inOrderTraversal(root->right);

}

---

Applications of Trees

1. File System: Trees are used to represent the hierarchical structure of files and directories.
2. Database Indexing: B-Trees and AVL Trees are used to implement database indexes, allowing efficient data retrieval.
3. Network Routing: Trees are used in network routing algorithms to find the shortest path.
4. XML/HTML Parsing: Trees are used to represent the structure of XML and HTML documents for parsing.
5. Game Development: Trees are used in AI for decision-making, such as in game trees.

Conclusion

Trees are a fundamental data structure in computer science, providing an efficient way to store and manipulate hierarchical data. Understanding the various types of trees and their operations is crucial for solving many computational problems.

---