Binary Search Tree

Search (root, item)  
Step 1 - if (item = root → data) or (root = NULL)  
return root  
else if (item < root → data)  
return Search(root → left, item)  
else  
return Search(root → right, item)  
END if  
Step 2 - END  

2. Insert Operation

A new key in binary search tree is inserted at the leaf . To inserting an element in BST, First we have to searching from the root node;In binary search tree whether the node to be inserted is less than the root node, then search for an empty location in the left subtree , else search for the empty location in the right subtree and insert the element.

 

Algorithm of Insert Operation

If node == NULL 
    return createNode(data)
if (data < node->data)
    node->left  = insert(node->left, data);
else if (data > node->data)
    node->right = insert(node->right, data);  
return node;

Program for inserting an element in C

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

struct node {
    int key;
    struct node *left, *right;
};

// create a new BST node
struct node* newNode(int item)
{
    struct node* temp
        = (struct node*)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

// inorder traversal of BST
void inorder(struct node* root)
{
    if (root != NULL) {
        inorder(root->left);
        printf("%d \n", root->key);
        inorder(root->right);
    }
}

// insert an element
struct node* insert(struct node* node, int key)
{
    if (node == NULL)
        return newNode(key);

    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);

    return node;
}

int main()
{
    
    struct node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    // inoder traversal of the BST
    inorder(root);

    return 0;
}

Output

20
30
40
50
60
70
80

 

Program for inserting an element in C++

#include <iostream>
using namespace std;

class BST
{
    int data;
    BST *left, *right;

public:
    // Default constructor.
    BST();

    // Parameterized constructor.
    BST(int);

    // Insert function.
    BST* Insert(BST*, int);

    // Inorder traversal.
    void Inorder(BST*);
};

// Default Constructor definition.
BST ::BST()
    : data(0)
    , left(NULL)
    , right(NULL)
{
}

// Parameterized Constructor definition.
BST ::BST(int value)
{
    data = value;
    left = right = NULL;
}

// Insert function definition.
BST* BST ::Insert(BST* root, int value)
{
    if (!root)
    {
        return new BST(value);
    }

    // Insert data.
    if (value > root->data)
    {
        .
        root->right = Insert(root->right, value);
    }
    else
    {
        root->left = Insert(root->left, value);
    }

    return root;
}


void BST ::Inorder(BST* root)
{
    if (!root) {
        return;
    }
    Inorder(root->left);
    cout << root->data << endl;
    Inorder(root->right);
}

int main()
{
    BST b, *root = NULL;
    root = b.Insert(root, 50);
    b.Insert(root, 30);
    b.Insert(root, 20);
    b.Insert(root, 40);
    b.Insert(root, 70);
    b.Insert(root, 60);
    b.Insert(root, 80);

    b.Inorder(root);
    return 0;
}

Output

20
30
40
50
60
70
80

 

Program for inserting an element in Python

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key



def insert(root, key):
    if root is None:
        return Node(key)
    else:
        if root.val == key:
            return root
        elif root.val < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, key)
    return root

#  inorder tree traversal


def inorder(root):
    if root:
        inorder(root.left)
        print(root.val)
        inorder(root.right)



r = Node(50)
r = insert(r, 30)
r = insert(r, 20)
r = insert(r, 40)
r = insert(r, 70)
r = insert(r, 60)
r = insert(r, 80)

inorder(r)

Output

20
30
40
50
60
70
80

Program for inserting an element in Java

class BinarySearchTree {

        class Node
    {
        int key;
        Node left, right;

        public Node(int item)
        {
            key = item;
            left = right = null;
        }
    }

    // Root of BST
    Node root;

    // Constructor
    BinarySearchTree()
    {
        root = null;
    }

    void insert(int key)
    {
        root = insertRec(root, key);
    }

    //insert a new key in BST 
    Node insertRec(Node root, int key)
    {

        
        if (root == null)
        {
            root = new Node(key);
            return root;
        }

        if (key < root.key)
            root.left = insertRec(root.left, key);
        else if (key > root.key)
            root.right = insertRec(root.right, key);

        return root;
    }

    void inorder()
    {
        inorderRec(root);
    }

    // inorder traversal of BST
    void inorderRec(Node root)
    {
        if (root != null) {
            inorderRec(root.left);
            System.out.println(root.key);
            inorderRec(root.right);
        }
    }

    public static void main(String[] args)
    {
        BinarySearchTree tree = new BinarySearchTree();

        
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        tree.inorder();
    }
}

Output

20
30
40
50
60
70
80

2. Deletion Operation

For insertion,we insert a leaf node so that we never had to worry about repositioning nodes in the tree.We cannot just remove a non-leaf node as it would disconnect part of the tree from the rest of tree.

There are three cases for deleting a node from a BST

Case I

Deletion Case1 : Leaf node

To delete a leaf node, simply change the appropripate child field in the nodes’s parent to point to null, instead of no node.

The node still exists, but is no longer a part of the tree.

Here suppose 4 is to deleted

 

 

Deleted node

Case II

Deletion : One Child

The node to be deleted in this case has only two connection:to its parent and to its only child. Connect the child of the node to the node’s parents, to cutting off the connection between node and its child, and between node and its parents

6 to be deleted

Copy the value of its child to the node and delete the child