Answers for "binary search tree program in c++"

binary search tree in cpp using class

/* Program to implement Binary Search Tree in c++ using classes  */
#include<iostream>
#include<stdlib.h>
#include<cstdlib>
using namespace std;

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

class BinaryTree {
    private:
        struct Node* root;
    public:
        BinaryTree() {
            root = NULL;
        }
        Node* createNode(int);
        Node* insertNode(Node*, int);
        Node* deleteNode(Node*, int);
        void inOrder(Node*);
        void preOrder(Node*);
        void postOrder(Node*);
        Node* findMinimum(Node*);

        Node* getRoot() {
            return root;
        }

        void setRoot(Node* ptr) {
            root = ptr; 
        }
};

Node* BinaryTree :: createNode(int n) {
    Node* newNode = new struct Node();
    newNode->data = n;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode; 
}


Node* BinaryTree :: findMinimum(Node* rootPtr) {
    while(rootPtr->left != NULL) {
        rootPtr = rootPtr->left;
    }
    return rootPtr;
}


Node* BinaryTree :: insertNode(Node* rootPtr, int n) {
    if(rootPtr == NULL) {
        return createNode(n);
    }
    if(n < rootPtr->data) {
        rootPtr->left = insertNode(rootPtr->left, n);
    }
    if(n > rootPtr->data) {
        rootPtr->right = insertNode(rootPtr->right, n);
    }
    return rootPtr;
}


Node* BinaryTree :: deleteNode(Node* rootPtr, int n) {
    if(rootPtr == NULL) {
        cout<<"Node to be deleted is not present.!"<<endl;
        return rootPtr;
    }
    else if(n < rootPtr->data) {
        rootPtr->left = deleteNode(rootPtr->left, n);
    } else if(n > rootPtr->data) {
        rootPtr->right = deleteNode(rootPtr->right, n);
    } else {
        if(rootPtr->left == NULL && rootPtr->right == NULL) {
            delete rootPtr;
            rootPtr = NULL;
        }
        else if(root->left == NULL) {
            struct Node* temp = rootPtr;
            rootPtr = rootPtr->right;
            delete temp;
        }
        else if(rootPtr->right == NULL) {
            struct Node* temp = rootPtr;
            rootPtr = rootPtr->left;
            delete temp;
        } else {
            Node* temp = findMinimum(rootPtr->right);
            rootPtr->data = temp->data;
            rootPtr->left = deleteNode(rootPtr->right, temp->data);
        }
    }

    return rootPtr;
}


void BinaryTree :: inOrder(Node* root) {
    if(root == NULL) {
        return;
    }
    inOrder(root->left);
    cout<<root->data<<"\t";
    inOrder(root->right);
}

void BinaryTree :: preOrder(Node* root) {
    if(root == NULL) return;
    cout<<root->data<<"\t";
    preOrder(root->left);
    preOrder(root->right);
}

void BinaryTree :: postOrder(Node* root) {
    if(root == NULL) return;
    postOrder(root->left);
    postOrder(root->right);
    cout<<root->data<<"\t";
}

int main() {
    BinaryTree l1;
    int ch, ele, res;
    Node* ptr;
    do {
            cout<<"1 - Insert Node\n";
            cout<<"2 - IN-ORDER Traversal\n";
            cout<<"3 - PRE-ORDER Traversal\n";
            cout<<"4 - POST-ORDER Traversal\n";
            cout<<"Enter choice\n";
            cin>>ch;
            switch(ch) {
                case 1: 
                    cout<<"Entre element to insert to the List\n";
                    cin>>ele;

                    ptr = l1.insertNode(l1.getRoot(), ele);
  
                    l1.setRoot(ptr);
                    break;
                case 2:
                    cout<<"---IN-ORDER TRAVERSAL---"<<endl;
                    l1.inOrder(l1.getRoot());
                    cout<<endl;
                    break;
                case 3:
                    cout<<"---PRE-ORDER TRAVERSAL---"<<endl;
                    l1.preOrder(l1.getRoot());
                    cout<<endl;
                    break;
                case 4:
                    cout<<"---POST-ORDER TRAVERSAL---"<<endl;
                    l1.postOrder(l1.getRoot());
                    cout<<endl;
                    break;
                case 5:
                    cout<<"Enter node to be deleted."<<endl;
                    cin>>ele;
                    ptr = l1.deleteNode(l1.getRoot(), ele);
                    l1.setRoot(ptr);
                default: cout<<"Invalid choice"<<endl;
            }
    } while(ch >=1 && ch <= 5);
    return 0;
}

binary search program c++

#include <iostream>
using namespace std;

// This program performs a binary search through an array, must be sorted to work
int binarySearch(int array[], int size, int value) 
{   
    int first = 0,         // First array element       
    last = size - 1,       // Last array element       
    middle,                // Mid point of search       
    position = -1;         // Position of search value   
    bool found = false;        // Flag   
    while (!found && first <= last) 
    {      
        middle = (first + last) / 2;     // Calculate mid point      
        if (array[middle] == value)      // If value is found at mid      
    	{         
                found = true;         
                position = middle;      
        }      
        else if (array[middle] > value)  // If value is in lower half         
            last = middle - 1;      
        else         
            first = middle + 1;          // If value is in upper half   
    }   
    return position;
}
int main ()
{
    const int size = 5; // size initialization
    int array[size] = {1, 2, 3, 4, 5}; // declare array of size 10
    int value; // declare value to be searched for
    int result; // declare variable that will be returned after binary search

    cout << "What value would you like to search for? "; // prompt user to enter value
    cin >> value;
    result = binarySearch(array, size, value);

    if (result == -1) // if value isn't found display this message
        cout << "Not found\n";
    else  // If value is found, displays message
        cout << "Your value is in the array.\n"; 
  
    return 0;
}

binary tree search

/* This is just the seaching function you need to write the required code.
	Thank you. */

void searchNode(Node *root, int data)
{
    if(root == NULL)
    {
        cout << "Tree is empty\n";
        return;
    }

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

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

        if(temp->data == data)
        {
            cout << "Node found\n";
            return;
        }

        if(temp->left != NULL)
            q.push(temp->left);
        if(temp->right != NULL)
            q.push(temp->right);
    }

    cout << "Node not found\n";
}

binary search tree program in c

// credit @callmemoeen

#include <stdio.h>
#include <stdlib.h>

#define NULL 0

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

typedef struct treeNode TN;

TN *root;

TN *Delete_aux(TN *t, int item);
void print_postorder(TN *t);
void print_inorder(TN *t);
void print_preorder(TN *t);
void Delete(int item);

void init_tree()
{
    root = NULL;
}

TN *createNode(int item)
{
    TN *temp = (TN *)malloc(sizeof(TN));
    temp->data = item;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

void print_tree_aux(TN *t, int depth)
{
    if (t == NULL)
        return;

    print_tree_aux(t->right, depth + 1);
    for (int i = 0; i < depth; i++)
        printf("\t");
    printf("%d---------------------------------\n", t->data);
    print_tree_aux(t->left, depth + 1);
}

void print_tree()
{
    printf("Printing tree ************************************\n");
    print_tree_aux(root, 0);
    printf("Complete ************************************\n");
}

TN *insert_aux(TN *t, int item)
{

    if (t == NULL)
    {
        return createNode(item);
    }

    if (item < t->data)
    {
        t->left = insert_aux(t->left, item);
        return t;
    }
    else
    {
        t->right = insert_aux(t->right, item);
        return t;
    }
}

void insert(int item)
{
    root = insert_aux(root, item);
}

TN *search_aux(TN *t, int key)
{
    if (t == NULL)
        return NULL;
    if (t->data == key)
        return t;
    else if (t->data > key)
        return search_aux(t->left, key);
    else
        return search_aux(t->right, key);
}

TN *search(int key)
{
    return search_aux(root, key);
}

TN *Leftmost(TN *t)
{
    TN *temp = t;
    while (temp->left != NULL)
    {
        temp = temp->left;
    }
    return temp;
}

TN *Delete_aux(TN *t, int item)
{
    TN *temp;
    // check if the tree is empty
    if (t == NULL)
        return NULL;
    // find the node with the arguement value recursively
    if (t->data > item)
    {
        t->left = Delete_aux(t->left, item);
        return t;
    }

    else if (t->data < item)
    {
        t->right = Delete_aux(t->right, item);
        return t;
    }
    else
    {
        // case 1: node with no child deletion
        if (t->left == NULL && t->right == NULL)
        {
            free(t);
            return NULL;
        }

        // case 2: 1 child only deletion. to be deleted node has a child on right branch
        else if (t->left == NULL)
        {
            temp = t->right;
            free(t);
            return temp;
        }
        // case 2: 1 child only deletion. to be deleted node has a child on left branch
        else if (t->right == NULL)
        {
            temp = t->left;
            free(t);
            return temp;
        }
        else
        {
            // get the smallest node in the right subtree temp = Leftmost(t->right)
            t->data = temp->data;
            t->right = Delete_aux(t->right, temp->data);
            return t;
        }
    }
}

void Delete(int item)
{
    TN *temp;
    // search() returns the node that contains the flag value
    temp = search(item);
    Delete_aux(root, item); 
}
void print_preorder(TN *t)
{
    if (t == NULL)
        return;

    printf("%d ", t->data);   // root
    print_preorder(t->left);  // left
    print_preorder(t->right); // right
}

void print_inorder(TN *t)
{
    if (t == NULL)
        return;

    print_inorder(t->left);  // left
    printf("%d ", t->data);  // root
    print_inorder(t->right); // right
}

void print_postorder(TN *t)
{
    if (t == NULL)
        return;

    print_postorder(t->left);  // left
    print_postorder(t->right); // right
    printf("%d ", t->data);    // root
}

int main()
{
    init_tree();

    insert(50);
    insert(30);
    insert(60);
    insert(20);
    insert(15);
    insert(5);
    insert(45);
    insert(75);
    insert(40);
    insert(90);
    insert(65);
    insert(70);
    print_tree(root, 0);

    if (search(65) == NULL)
        printf("%d not found\n", 65);
    else
        printf("%d found\n", 65);

    if (search(95) == NULL)
        printf("%d not found\n", 95);
    else
        printf("%d found\n", 95);

    print_inorder(root);
    printf("\n");

    print_preorder(root);
    printf("\n");

    print_postorder(root);
    printf("\n");

    Delete(5);
    print_tree();

    Delete(70);
    print_tree();

    return 0;
}