Trees

Trees in C++

A tree is a hierarchical data structure that consists of nodes connected by edges. It is widely used to represent data that has a hierarchical structure, such as organizational charts, file systems, or parsing expressions. Each tree consists of nodes, where each node contains:

• Data: The value stored in the node.
• Child Nodes: Zero or more nodes connected to the current node (called children).

A root node is the topmost node of the tree, and the leaf nodes are those that do not have any children.

Key Terminology in Trees

1. Root: The top node of the tree (no parent).
2. Node: An individual element in the tree, containing data and references to its children.
3. Parent: A node that has one or more child nodes.
4. Child: A node that is a descendant of another node (i.e., linked from another node).
5. Leaf Node: A node with no children.
6. Subtree: A tree formed by a node and its descendants.
7. Depth of a node: The number of edges from the root to the node.
8. Height of a node: The number of edges on the longest path from the node to a leaf.
9. Level: The level of a node is the number of edges from the root to the node.

Types of Trees

1. Binary Tree: Each node has at most two children, referred to as the left and right child.
2. Binary Search Tree (BST): A type of binary tree where the left child node’s value is smaller than its parent’s value, and the right child node’s value is greater than its parent’s value.
3. Balanced Binary Search Tree: A binary search tree where the difference between the heights of the left and right subtrees of any node is at most one.
4. AVL Tree: A self-balancing binary search tree.
5. Heap: A complete binary tree that satisfies the heap property, either max-heap or min-heap.
6. Trie (Prefix Tree): A type of tree used for storing strings in a way that allows efficient retrieval based on prefixes.

Basic Tree Operations

• Traversal: Visiting all nodes in a specific order.

  • Pre-order: Visit the root, then the left subtree, then the right subtree.
  • In-order: Visit the left subtree, then the root, then the right subtree.
  • Post-order: Visit the left subtree, then the right subtree, then the root.
  • Level-order: Visit all nodes level by level (typically implemented using a queue).

• Insertion: Adding a node to the tree.

• Deletion: Removing a node from the tree.

• Searching: Finding a node with a specific value.

1. Binary Tree in C++

A binary tree is a tree in which each node has at most two children (left and right). It is often used as a base for more advanced trees like binary search trees or heaps.

Binary Tree Node Structure

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;

    // Constructor to create a new node
    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

class BinaryTree {
private:
    Node* root;

    // Preorder Traversal (Root -> Left -> Right)
    void preorder(Node* node) {
        if (node != nullptr) {
            cout << node->data << " ";
            preorder(node->left);
            preorder(node->right);
        }
    }

    // Inorder Traversal (Left -> Root -> Right)
    void inorder(Node* node) {
        if (node != nullptr) {
            inorder(node->left);
            cout << node->data << " ";
            inorder(node->right);
        }
    }

    // Postorder Traversal (Left -> Right -> Root)
    void postorder(Node* node) {
        if (node != nullptr) {
            postorder(node->left);
            postorder(node->right);
            cout << node->data << " ";
        }
    }

    // Level Order Traversal (Breadth-first, using queue)
    void levelOrder() {
        if (root == nullptr) return;
        queue<Node*> q;
        q.push(root);
        while (!q.empty()) {
            Node* node = q.front();
            q.pop();
            cout << node->data << " ";
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }

public:
    BinaryTree() : root(nullptr) {}

    // Function to insert nodes in the tree
    void insert(int value) {
        Node* newNode = new Node(value);
        if (root == nullptr) {
            root = newNode;
            return;
        }

        // Perform level order insertion to make the tree complete
        queue<Node*> q;
        q.push(root);
        while (!q.empty()) {
            Node* temp = q.front();
            q.pop();

            if (temp->left == nullptr) {
                temp->left = newNode;
                return;
            } else {
                q.push(temp->left);
            }

            if (temp->right == nullptr) {
                temp->right = newNode;
                return;
            } else {
                q.push(temp->right);
            }
        }
    }

    // Wrapper functions for traversals
    void preorderTraversal() {
        preorder(root);
        cout << endl;
    }

    void inorderTraversal() {
        inorder(root);
        cout << endl;
    }

    void postorderTraversal() {
        postorder(root);
        cout << endl;
    }

    void levelOrderTraversal() {
        levelOrder();
        cout << endl;
    }
};

int main() {
    BinaryTree tree;

    // Insert nodes in the binary tree
    tree.insert(1);
    tree.insert(2);
    tree.insert(3);
    tree.insert(4);
    tree.insert(5);
    tree.insert(6);
    tree.insert(7);

    // Traverse the tree
    cout << "Pre-order Traversal: ";
    tree.preorderTraversal(); // Output: 1 2 4 5 3 6 7 

    cout << "In-order Traversal: ";
    tree.inorderTraversal(); // Output: 4 2 5 1 6 3 7 

    cout << "Post-order Traversal: ";
    tree.postorderTraversal(); // Output: 4 5 2 6 7 3 1 

    cout << "Level-order Traversal: ";
    tree.levelOrderTraversal(); // Output: 1 2 3 4 5 6 7

    return 0;
}

2. Binary Search Tree (BST) in C++

A binary search tree (BST) is a binary tree where for each node:

• All values in the left subtree are smaller than the node's value.
• All values in the right subtree are greater than the node's value.

This property makes searching, insertion, and deletion operations more efficient (on average).

Binary Search Tree Node Structure

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;

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

class BinarySearchTree {
private:
    Node* root;

    // Insert a value in the BST
    Node* insert(Node* node, int value) {
        if (node == nullptr) return new Node(value);

        if (value < node->data) {
            node->left = insert(node->left, value);
        } else if (value > node->data) {
            node->right = insert(node->right, value);
        }

        return node;
    }

    // Search for a value in the BST
    bool search(Node* node, int value) {
        if (node == nullptr) return false;

        if (value == node->data) return true;
        else if (value < node->data) return search(node->left, value);
        else return search(node->right, value);
    }

    // In-order Traversal
    void inorder(Node* node) {
        if (node != nullptr) {
            inorder(node->left);
            cout << node->data << " ";
            inorder(node->right);
        }
    }

public:
    BinarySearchTree() : root(nullptr) {}

    void insert(int value) {
        root = insert(root, value);
    }

    bool search(int value) {
        return search(root, value);
    }

    void inorderTraversal() {
        inorder(root);
        cout << endl;
    }
};

int main() {
    BinarySearchTree bst;

    // Insert values into the BST
    bst.insert(50);
    bst.insert(30);
    bst.insert(70);
    bst.insert(20);
    bst.insert(40);
    bst.insert(60);
    bst.insert(80);

    // In-order traversal (should print values in sorted order)
    cout << "In-order Traversal: ";
    bst.inorderTraversal(); // Output: 20 30 40 50 60 70 80

    // Search for a value
    cout << "Search for 40: " << (bst.search(40) ? "Found" : "Not Found") << endl; // Found
    cout << "Search for 25: " << (bst.search(25