Answer to Question #286156 in C++ for Abubakar Tanveer

Question

Implement the following binary search tree operations:

1. BFS

2. DFS

3. Addition

4. Deletion

Answer 1

#include <bits/stdc++.h>
using namespace std;


class node {
public:
    int data;
    node *left, *right;
};


void currentLevel(node* root, int level);
int height(node* node);
node* newNode(int data);


void printLevelOrder(node* root)
{
    int h = height(root);
    int i;
    for (i = 1; i <= h; i++)
        currentLevel(root, i);
}


void currentLevel(node* root, int level)
{
    if (root == NULL)
        return;
    if (level == 1)
        cout << root->data << " ";
    else if (level > 1) {
        currentLevel(root->left, level - 1);
        currentLevel(root->right, level - 1);
    }
}


int height(node* node)
{
    if (node == NULL)
        return 0;
    else {
        int lheight = height(node->left);
        int rheight = height(node->right);


        if (lheight > rheight) {
            return (lheight + 1);
        }
        else {
            return (rheight + 1);
        }
    }
}


node* newNode(int data)
{
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;


    return (Node);
}


int main()
{
    node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);


    printLevelOrder(root);


    return 0;
}


// C++ program to insert element in Binary Tree
#include <iostream>
#include <queue>
using namespace std;


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


Node* CreateNode(int data)
{
    Node* newNode = new Node();
    if (!newNode) {
        cout << "Memory error\n";
        return NULL;
    }
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}


Node* InsertNode(Node* root, int data)
{
    if (root == NULL) {
        root = CreateNode(data);
        return root;
    }


    queue<Node*> q;
    q.push(root);


    while (!q.empty()) {
        Node* temp = q.front();
        q.pop();


        if (temp->left != NULL)
            q.push(temp->left);
        else {
            temp->left = CreateNode(data);
            return root;
        }


        if (temp->right != NULL)
            q.push(temp->right);
        else {
            temp->right = CreateNode(data);
            return root;
        }
    }
}


void foobar(Node* temp)
{
    if (temp == NULL)
        return;


    foobar(temp->left);
    cout << temp->data << ' ';
    foobar(temp->right);
}


int main()
{
    Node* root = CreateNode(10);
    root->left = CreateNode(11);
    root->left->left = CreateNode(7);
    root->right = CreateNode(9);
    root->right->left = CreateNode(15);
    root->right->right = CreateNode(8);


    foobar(root);
    return 0;
}