27. DSA with C++ - implement binary tree in C++ with various operations

implement binary tree in c++ with various operations:

#include <iostream>

// Node structure for the binary tree
struct Node {
    int data;
    Node* left;
    Node* right;
};

// Function to create a new node
Node* createNode(int value) {
    Node* newNode = new Node;
    newNode->data = value;
    newNode->left = nullptr;
    newNode->right = nullptr;
    return newNode;
}

// Function to insert a node into the binary tree
Node* insertNode(Node* root, int value) {
    if (root == nullptr) {
        return createNode(value);
    }
    if (value < root->data) {
        root->left = insertNode(root->left, value);
    } else if (value > root->data) {
        root->right = insertNode(root->right, value);
    }
    return root;
}

// Function to search for a value in the binary tree
bool searchValue(Node* root, int value) {
    if (root == nullptr) {
        return false;
    }
    if (value == root->data) {
        return true;
    } else if (value < root->data) {
        return searchValue(root->left, value);
    } else {
        return searchValue(root->right, value);
    }
}

// Function to perform an inorder traversal of the binary tree
void inorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }
    inorderTraversal(root->left);
    std::cout << root->data << " ";
    inorderTraversal(root->right);
}

// Function to delete a node from the binary tree
Node* deleteNode(Node* root, int value) {
    if (root == nullptr) {
        return root;
    }
    if (value < root->data) {
        root->left = deleteNode(root->left, value);
    } else if (value > root->data) {
        root->right = deleteNode(root->right, value);
    } 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* successor = root->right;
        while (successor->left != nullptr) {
            successor = successor->left;
        }
        root->data = successor->data;
        root->right = deleteNode(root->right, successor->data);
    }
    return root;
}

int main() {
    Node* root = nullptr;

    // Insert nodes into the binary tree
    root = insertNode(root, 50);
    root = insertNode(root, 30);
    root = insertNode(root, 20);
    root = insertNode(root, 40);
    root = insertNode(root, 70);
    root = insertNode(root, 60);
    root = insertNode(root, 80);

    // Perform an inorder traversal of the binary tree
    std::cout << "Inorder Traversal: ";
    inorderTraversal(root); // Output: 20 30 40 50 60 70 80
    std::cout << std::endl;

    // Search for a value in the binary tree
    int searchValue = 40;
    if (searchValue(root, searchValue)) {
        std::cout << "Value " << searchValue << " found in the binary tree." << std::endl;
    } else {
        std::cout << "Value " <<

 searchValue << " not found in the binary tree." << std::endl;
    }

    // Delete a node from the binary tree
    int deleteValue = 30;
    root = deleteNode(root, deleteValue);
    std::cout << "Inorder Traversal after deleting " << deleteValue << ": ";
    inorderTraversal(root); // Output: 20 40 50 60 70 80
    std::cout << std::endl;

    // Clean up memory (optional)
    // Note: Recursive deletion can be implemented separately to handle the entire tree deletion.

    return 0;
}
  

• In this implementation, we have a Node structure that represents a node in the binary tree. Each node contains an integer data value and pointers to its left and right child nodes.
• The createNode function is used to create a new node with the given value and initializes the left and right pointers to nullptr.
• The insertNode function inserts a node into the binary tree. It compares the value with the current node and recursively inserts it into the left subtree if the value is less than the current node's value, or into the right subtree if the value is greater.
• The searchValue function searches for a value in the binary tree. It starts from the root and compares the value with the current node's value. If the value is found, it returns true; otherwise, it recursively searches in the left or right subtree based on the value.
• The inorderTraversal function performs an inorder traversal of the binary tree. It first traverses the left subtree, then visits the current node, and finally traverses the right subtree. In this example, the function prints the data of each node.
• The deleteNode function deletes a node from the binary tree. It first searches for the node to be deleted, and once found, handles three cases: (1) the node has no child, (2) the node has only one child, or (3) the node has two children. The function recursively adjusts the tree structure and deletes the appropriate node.
• In the main function, we create a binary tree by inserting nodes with specific values. We then perform an inorder traversal to print the data of the nodes. Additionally, we demonstrate searching for a value in the tree and deleting a node from the tree.
• Remember to free the memory allocated for the nodes by using delete for each node in the tree at the end of the program. Recursive deletion can be implemented separately to handle the entire tree deletion if needed.