by Jasleen Chhabra | Updated on 24 August 2024

Insertion in trees is a fundamental operation that enables the construction and maintenance of various types of trees. This guide will cover the insertion process in Binary Trees, Binary Search Trees (BSTs), AVL Trees, and B-Trees, offering insights into their algorithms and implementations.

---

Inserting into a Binary Tree

A binary tree is a tree data structure where each node has at most two children, referred to as the left child and the right child. Insertion in a binary tree typically follows a level-order traversal method to maintain its structure.

Algorithm for Insertion in a Binary Tree:

1. Start at the root.
2. If the root is null, insert the new node as the root.
3. Use a queue to traverse the tree level by level.
4. If the current node has no left child, insert the new node as the left child.
5. If the current node has no right child, insert the new node as the right child.
6. If both children are present, enqueue the children and continue.

C++ Implementation:

#include <iostream>

#include <queue>

 

struct Node {

    int data;

    Node* left;

    Node* right;

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

};

 

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

    if (root == nullptr) {

        root = new Node(key);

        return;

    }

    std::queue<Node*> q;

    q.push(root);

    while (!q.empty()) {

        Node* temp = q.front();

        q.pop();

        if (temp->left == nullptr) {

            temp->left = new Node(key);

            break;

        } else {

            q.push(temp->left);

        }

        if (temp->right == nullptr) {

            temp->right = new Node(key);

            break;

        } else {

            q.push(temp->right);

        }

    }

}

 

void inOrderTraversal(Node* root) {

    if (root == nullptr) return;

    inOrderTraversal(root->left);

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

    inOrderTraversal(root->right);

}

 

int main() {

    Node* root = nullptr;

    insert(root, 10);

    insert(root, 20);

    insert(root, 30);

    insert(root, 40);

    insert(root, 50);

    

    std::cout << "In-order traversal of the tree: ";

    inOrderTraversal(root);

    return 0;

}

---

Inserting into a Binary Search Tree (BST)

A Binary Search Tree (BST) is a binary tree in which each node has a value greater than all values in its left subtree and less than all values in its right subtree.

Algorithm for Insertion in a BST:

1. Start at the root.
2. If the root is null, insert the new node as the root.
3. Recursively compare the new value with the current node's value.
4. If the new value is less, go to the left subtree; if greater, go to the right subtree.
5. Insert the new node in the appropriate position.

C++ Implementation:

struct BSTNode {

    int data;

    BSTNode* left;

    BSTNode* right;

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

};

 

BSTNode* insertBST(BSTNode* root, int key) {

    if (root == nullptr) {

        return new BSTNode(key);

    }

    if (key < root->data) {

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

    } else {

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

    }

    return root;

}

 

void inOrderTraversalBST(BSTNode* root) {

    if (root == nullptr) return;

    inOrderTraversalBST(root->left);

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

    inOrderTraversalBST(root->right);

}

 

int main() {

    BSTNode* root = nullptr;

    root = insertBST(root, 50);

    insertBST(root, 30);

    insertBST(root, 20);

    insertBST(root, 40);

    insertBST(root, 70);

    insertBST(root, 60);

    insertBST(root, 80);

   

    std::cout << "In-order traversal of the BST: ";

    inOrderTraversalBST(root);

    return 0;

}

---

Inserting into an AVL Tree

An AVL Tree is a self-balancing Binary Search Tree (BST) where the difference in heights between the left and right subtrees cannot be more than one for all nodes.

Algorithm for Insertion in an AVL Tree:

1. Insert the node as in a BST.
2. Update the height of the ancestor nodes.
3. Check the balance factor of the ancestor nodes.
4. If the tree becomes unbalanced, perform appropriate rotations (LL, LR, RR, RL).

C++ Implementation:

struct AVLNode {

    int data;

    AVLNode* left;

    AVLNode* right;

    int height;

    AVLNode(int value) : data(value), left(nullptr), right(nullptr), height(1) {}

};

 

int height(AVLNode* node) {

    return node ? node->height : 0;

}

 

int getBalanceFactor(AVLNode* node) {

    return node ? height(node->left) - height(node->right) : 0;

}

 

AVLNode* rightRotate(AVLNode* y) {

    AVLNode* x = y->left;

    AVLNode* T2 = x->right;

    x->right = y;

    y->left = T2;

    y->height = std::max(height(y->left), height(y->right)) + 1;

    x->height = std::max(height(x->left), height(x->right)) + 1;

    return x;

}

 

AVLNode* leftRotate(AVLNode* x) {

    AVLNode* y = x->right;

    AVLNode* T2 = y->left;

    y->left = x;

    x->right = T2;

    x->height = std::max(height(x->left), height(x->right)) + 1;

    y->height = std::max(height(y->left), height(y->right)) + 1;

    return y;

}

 

AVLNode* insertAVL(AVLNode* node, int key) {

    if (node == nullptr) return new AVLNode(key);

    if (key < node->data) {

        node->left = insertAVL(node->left, key);

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

        node->right = insertAVL(node->right, key);

    } else {

        return node;

    }

    node->height = 1 + std::max(height(node->left), height(node->right));

    int balance = getBalanceFactor(node);

    if (balance > 1 && key < node->left->data) return rightRotate(node);

    if (balance < -1 && key > node->right->data) return leftRotate(node);

    if (balance > 1 && key > node->left->data) {

        node->left = leftRotate(node->left);

        return rightRotate(node);

    }

    if (balance < -1 && key < node->right->data) {

        node->right = rightRotate(node->right);

        return leftRotate(node);

    }

    return node;

}

 

void inOrderTraversalAVL(AVLNode* root) {

    if (root == nullptr) return;

    inOrderTraversalAVL(root->left);

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

    inOrderTraversalAVL(root->right);

}

 

int main() {

    AVLNode* root = nullptr;

    root = insertAVL(root, 10);

    root = insertAVL(root, 20);

    root = insertAVL(root, 30);

    root = insertAVL(root, 40);

    root = insertAVL(root, 50);

    root = insertAVL(root, 25);

   

    std::cout << "In-order traversal of the AVL Tree: ";

    inOrderTraversalAVL(root);

    return 0;

}

---

Inserting into a B-Tree

A B-Tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.

Algorithm for Insertion in a B-Tree:

1. If the tree is empty, create a root node.
2. Traverse the tree to find the appropriate leaf node.
3. Insert the key into the leaf node.
4. If the leaf node overflows, split the node and propagate the split upwards.

C++ Implementation:

#include <iostream>

#include <vector>

 

class BTreeNode {

    std::vector<int> keys;

    std::vector<BTreeNode*> children;

    int t;

    bool leaf;

 

public:

    BTreeNode(int _t, bool _leaf);

    void insertNonFull(int k);

    void splitChild(int i, BTreeNode* y);

    void traverse();

    friend class BTree;

};

 

class BTree {

    BTreeNode* root;

    int t;

   

public:

    BTree(int _t) : root(nullptr), t(_t) {}

    void traverse() {

        if (root != nullptr) root->traverse();

    }

    void insert(int k);

};

 

BTreeNode::BTreeNode(int t1, bool leaf1) : t(t1), leaf(leaf1) {}

 

void BTreeNode::insertNonFull(int k) {

    int i = keys.size() - 1;

    if (leaf) {

        keys.push_back(0);

        while (i >= 0 && keys[i] > k) {

            keys[i + 1] = keys[i];

            i--;

        }

        keys[i + 1] = k;

    } else {

        while (i >= 0 && keys[i] > k) i--;

        if (children[i + 1]->keys.size() == 2 * t - 1) {

            splitChild(i + 1, children[i + 1]);

            if (keys[i + 1] < k) i++;

        }

        children[i + 1]->insertNonFull(k);

    }

}

 

void BTreeNode::splitChild(int i, BTreeNode* y) {

    BTreeNode* z = new BTreeNode(y->t, y->leaf);

    for (int j = 0; j < t - 1; j++) z->keys.push_back(y->keys[j + t]);

    if (!y->leaf) {

        for (int j = 0; j < t; j++) z->children.push_back(y->children[j + t]);

    }

    y->keys.resize(t - 1);

    children.insert(children.begin() + i + 1, z);

    keys.insert(keys.begin() + i, y->keys[t - 1]);

}

 

void BTreeNode::traverse() {

    int i;

    for (i = 0; i < keys.size(); i++) {

        if (!leaf) children[i]->traverse();

        std::cout << " " << keys[i];

    }

    if (!leaf) children[i]->traverse();

}

 

void BTree::insert(int k) {

    if (root == nullptr) {

        root = new BTreeNode(t, true);

        root->keys.push_back(k);

    } else {

        if (root->keys.size() == 2 * t - 1) {

            BTreeNode* s = new BTreeNode(t, false);

            s->children.push_back(root);

            s->splitChild(0, root);

            int i = 0;

            if (s->keys[0] < k) i++;

            s->children[i]->insertNonFull(k);

            root = s;

        } else {

            root->insertNonFull(k);

        }

    }

}

 

int main() {

    BTree t(3);

    t.insert(10);

    t.insert(20);

    t.insert(5);

    t.insert(6);

    t.insert(12);

    t.insert(30);

    t.insert(7);

    t.insert(17);

   

    std::cout << "Traversal of the B-Tree is: ";

    t.traverse();

    return 0;

}

---

Conclusion

Insertion in trees is a critical operation that forms the foundation of building and maintaining various tree structures. Understanding the algorithms and implementations for different types of trees, such as Binary Trees, Binary Search Trees, AVL Trees, and B-Trees, equips you with the knowledge to handle hierarchical data efficiently.

---