Scribd Logo
Upload

Welcome to Scribd!

  • 2 views

    Binary Search Tree Implementation

    Uploaded by

    vahini

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Binary Search Tree Implementation

    Uploaded by

    vahini
    2 views4 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    2 views4 pages

    Binary Search Tree Implementation

    Uploaded by

    vahini

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 4

    // Binary

    Search Tree
    -
    Implemenati
    on in C++
    // Simple program to create a BST of integers and search an
    element in it
    #include<iostream>
    using namespace std;
    //Definition of Node for Binary search tree
    struct BstNode {
    int data;
    BstNode* left;
    BstNode* right;
    };

    // Function to create a new Node in heap


    BstNode* GetNewNode(int data) {
    BstNode* newNode = new BstNode();
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
    }

    // To insert data in BST, returns address of root node


    BstNode* Insert(BstNode* root,int data) {
    if(root == NULL) { // empty tree
    root = GetNewNode(data);
    }
    // if data to be inserted is lesser, insert in left subtree.
    else if(data <= root->data) {
    root->left = Insert(root->left,data);
    }
    // else, insert in right subtree.
    else {
    root->right = Insert(root->right,data);
    }
    return root;
    }
    //To search an element in BST, returns true if element is found
    bool Search(BstNode* root,int data) {
    if(root == NULL) {
    return false;
    }
    else if(root->data == data) {
    return true;
    }
    else if(data <= root->data) {
    return Search(root->left,data);
    }
    else {
    return Search(root->right,data);
    }
    }
    int main() {
    BstNode* root = NULL; // Creating an empty tree
    /*Code to test the logic*/
    root = Insert(root,15);
    root = Insert(root,10);
    root = Insert(root,20);
    root = Insert(root,25);
    root = Insert(root,8);
    root = Insert(root,12);
    // Ask user to enter a number.
    int number;
    cout<<"Enter number be searched\n";
    cin>>number;
    //If number is found, print "FOUND"
    if(Search(root,number) == true) cout<<"Found\n";
    else cout<<"Not Found\n";
    }

    #include <iostream>
    class BSTNode
    {
    private:
    int data;
    BSTNode* left;
    BSTNode* right;
    public:
    BSTNode(int data)
    {
    this -> data = data;
    this -> left = NULL;
    this -> right = NULL;
    }
    ~BSTNode();

    void insert(int data)


    {
    if (data <= this -> data)
    {
    if (this -> left == NULL)
    {
    this -> left = new BSTNode(data);
    }
    else
    {
    this -> left -> insert(data);
    }
    }
    else
    {
    if (this -> right == NULL)
    {
    this -> right = new BSTNode(data);
    }
    else
    {
    this -> right -> insert(data);
    }
    }

    void print_node ()
    {
    std::cout << "Value at the node: " << this -> data << std::endl;
    if (this -> left != NULL)
    std::cout << "Value at left node: " << this -> left -> data
    << std::endl;
    if (this -> right != NULL)
    std::cout << "Value at right node: " << this -> right -> data
    << std::endl;
    }

    bool find(int val)


    {
    if (this -> data == val)
    {
    std::cout << "Found" << std::endl;
    return true;
    }
    else if (val <= this -> data)
    {
    if (this -> left == NULL)
    {
    std::cout << "Not found" << std::endl;
    return false;
    }
    else
    {
    return (this -> left) -> find(val);
    }
    }
    else
    {
    //std::cout << "It's here" << std::endl;
    if (this -> right == NULL)
    {
    std::cout << "Not found" << std::endl;
    return false;
    }
    else
    {
    //std::cout << "passing" << std::endl;
    return (this -> right) -> find(val);
    }
    }
    std::cout << "Something wrong while trying to find" << std::endl;
    return false;
    }
    };

    int main()
    {
    BSTNode* root = new BSTNode(10);
    root -> print_node();
    root -> insert(9);
    root -> insert(7);
    root -> insert(6);
    root -> print_node();
    root -> insert(14);
    root -> print_node();
    std::cout << "Finding 10: " << root -> find(10) << std::endl;
    std::cout << "Finding 8: " << root -> find(8) << std::endl;
    root -> insert(19);
    root -> insert(70);
    root -> insert(3);
    root -> print_node();
    root -> insert(4);
    root -> insert(8);
    root -> print_node();
    std::cout << "Finding 70: " << root -> find(70) << std::endl;
    std::cout << "Finding 8: " << root -> find(8) << std::endl;
    std::cout << "Finding 17: " << root -> find(17) << std::endl;
    }

    You might also like