Answers for "binary search tree c++ implementation"

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 search in c++

#include<iostream> 
using namespace std; 
int binarySearch(int arr[], int p, int r, int num) { 
   if (p <= r) { 
      int mid = (p + r)/2; 
      if (arr[mid] == num)   
         return mid ; 
      if (arr[mid] > num)  
         return binarySearch(arr, p, mid-1, num);            
      if (arr[mid] < num)
         return binarySearch(arr, mid+1, r, num); 
   } 
   return -1; 
} 
int main(void) { 
   int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40}; 
   int n = sizeof(arr)/ sizeof(arr[0]); 
   int num = 33; 
   int index = binarySearch (arr, 0, n-1, num); 
   if(index == -1)
      cout<< num <<" is not present in the array";
   else
      cout<< num <<" is present at index "<< index <<" in the array"; 
   return 0; 
}

python code for binary search tree

#Complete Binary Search Tree Using Python 3

class node:
    def  __init__(self,data):
        self.data=data
        self.left=None
        self.right=None

class binarytree:
    def __init__(self):
        self.root=None

#INSERT

    def insert(self,data):
        if self.root==None:				
            self.root=node(data)
        else:
            self._insert(data,self.root)
    def _insert(self,data,cur_node):
        if data<cur_node.data:
            if cur_node.left==None:			
                cur_node.left=node(data)
            else:
                self._insert(data,cur_node.left) 
        elif data>cur_node.data:			
            if cur_node.right==None:
                cur_node.right=node(data)
            else:
                self._insert(data,cur_node.right)
        else:
            print('Data In Treee Already')

#REMOVE

    def remove(self,data):
        if self.root!=None:
            self._remove(data,self.root)
    def _remove(self,data,cur_node):
        if cur_node == None:
            return cur_node
        if data<cur_node.data:
            cur_node.left=self._remove(data,cur_node.left)
        elif data>cur_node.data:
            cur_node.right=self._remove(data,cur_node.right)
        else:
            if cur_node.left is None and cur_node.right is None:
                print('Removing Leaf Node')
                if cur_node==self.root:
                    self.root=None
                del cur_node
                return None
            if cur_node.left is None:
                print('Removing None with Right Child')
                if cur_node==self.root:
                    self.root=cur_node.right
                tempnode=cur_node.right
                del cur_node
                return tempnode
            elif cur_node.right is None:
                print('Removing None with Left Child')
                if cur_node==self.root:
                    self.root=cur_node.left
                tempnode=cur_node.left
                del cur_node
                return tempnode
            print('Removing Node with 2 Children')
            tempnode=self.getpred(cur_node.left)
            cur_node.data=tempnode.data
            cur_node.left=self._remove(cur_node.data,cur_node.left)
        return cur_node
    def getpred(self,cur_node):
        if cur_node.right!=None:
            return self.getpred(cur_node.right)
        return cur_node

#INORDER TRAVERSAL

    def inorder(self):
        if self.root!=None:
            self._inorder(self.root)
    def _inorder(self,cur_node):
        if cur_node!=None:
            self._inorder(cur_node.left)
            print(cur_node.data)
            self._inorder(cur_node.right)

#PREORDER TRAVERSAL

    def preorder(self):
        if self.root!=None:
            self._preorder(self.root)
    def _preorder(self,cur_node):
        if cur_node!=None:
            print(cur_node.data)
            self._preorder(cur_node.left)
            self._preorder(cur_node.right)

#POSTORDER TRAVERSAL

    def postorder(self):
        if self.root!=None:
            self._postorder(self.root)
    def _postorder(self,cur_node):
        if cur_node!=None:
            self._postorder(cur_node.left)
            self._postorder(cur_node.right)
            print(cur_node.data)

#MINIMUM VALUE

    def minval(self):
        if self.root!=None:
            return self._minval(self.root)
    def _minval(self,cur_node):
        if cur_node.left!=None:
            return self._minval(cur_node.left)
        return cur_node.data

#MAXIMUM VALUE

    def maxval(self):
        if self.root!=None:
            return self._maxval(self.root)
    def _maxval(self,cur_node):
        if cur_node.right!=None:
            return self._maxval(cur_node.right)
        return cur_node.data

tree=binarytree()

tree.insert(100)
tree.insert(90)					#			 100
tree.insert(110)				#			/	\
tree.insert(95)					#          90   110
tree.insert(30)					#		  /  \
								#		30    95 
tree.remove(110)
tree.remove(90)

tree.inorder()
#tree.preorder()
#tree.postorder()

print(tree.minval())
print(tree.maxval())

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";
}

insert binary search tree

void BSNode::insert(std::string value) {

	if (this->_data == value) {
		_count++;
		return;
	}

	if (this->_data > value) {
		if (this->getLeft() == nullptr) {
			this->_left = new BSNode(value);
		}
		this->getLeft()->insert(value);
		return;
	}

	if (this->getRight() == nullptr) {
		this->_right = new BSNode(value);
		return;
	}
	this->getRight()->insert(value);
}