JIYIK CN >

A binary search tree (BST) is an ordered binary tree data structure based on nodes. A node has a value and two child nodes (a binary tree has at most two child nodes) connected to each other. A node has a value and two child nodes (a binary tree has at most two child nodes) connected to each other. Except for the root node, all nodes can only be referenced by their parent node. A BST has the following properties.

• All nodes in the left subtree are smaller than the root node.
• All nodes in the right subtree are larger than the root node.
• The left and right subtrees must also be binary search trees.

Since it is an ordered data structure, the input elements are always organized in a sorted manner. We can use in-order traversal to retrieve the data stored in BST in a sorted manner. It gets its name because, just like binary search, it can be used to search for O(logn)data in .

Search operations in a binary search tree

We know that in a BST, the elements to the right of the root are larger, so if the target element we are searching for is smaller than the root, then the entire right subtree can be ignored. Similarly, if the element is larger than the root, then the left subtree can also be ignored. We move in a similar way until we run out of trees or find the target element as the root of the subtree. If the BST is balanced (a tree is called a balanced tree if the difference between the height of the left and right subtrees is less than or equal to 1 for all nodes), then the search inside the BST is performed similarly to a binary search, because both subtrees have about half of the elements that are ignored at each iteration, but if it is an unbalanced tree, all the nodes may exist on the same side and the search may be performed similar to a linear search.

Binary Search Tree Search Algorithm

Assume rootthat is the root node of BST and Xis the target element to be searched.

• If root== NULL, return NULL.
• if X== root->data, return root;
• If X< root->data, return search(root->left).
• If X> root->data, return search(root->right).

Binary Search Tree Search Description

Suppose we have the BST above, and we want to find the element X= 25.

• Compare the root element with and Xfind 41> 25, so discard the right half and move to the left subtree.
• The root of the left subtree 23is < 25, so discard its left subtree and move to the right.
• The new root 28< 25, so move left, find our element Xequal to 25and return the node.

Inserting an element into a binary search tree

The algorithm to insert an element in a BST is very similar to the algorithm to search an element in a BST, in that before inserting an element, we have to find its correct position, the only difference between the insertion and search functionality is that in case of search, we return the node containing the target value, whereas in case of insertion, we create a new node at the appropriate place of the node.

BST Insertion Algorithm

Assume rootthat is the root node of BST and Xis the element we want to insert.

• If root== NULL, return a newly formed node, data= X.
• if ( X< root->data), root->left= insert(root->left, X);
• else if ( X> root->data) , root->right= insert(root->right, X).
• Returns a rootpointer to the original .

BST Insertion Instructions

• First, we rootinitialize the BST by creating a node and insert it into it 5.
• 3is smaller than 5, so it is inserted 5to the left of .
• 4is smaller than 5, but 3larger than , so insert 3to the right of , but insert 4to the left of .
• 2is the smallest element in the current tree, so it is inserted at the leftmost position.
• 1is the smallest element in the current tree, so it is inserted at the leftmost position.
• 6is the largest element in the current tree, so it is inserted at the rightmost position.

This is how we insert elements in a BST.

Implementation of BST search and insertion

#include <iostream>
using namespace std;

class Node {
public:
    int key;
    Node *left, *right;
};

Node *newNode(int item) {
    Node *temp = (Node *)malloc(sizeof(Node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

void inorder(Node *root) {
    if (root != NULL) {
        inorder(root->left);
        cout << root->key << " ";
        inorder(root->right);
    }
}

Node* insert(Node *root, int key) {
    if (root == NULL)
        return newNode(key);
    if (key < root->key)
        root->left = insert(root->left, key);
    else
        root->right = insert(root->right, key);

    return root;
}

Node* search(Node* root, int key)
{
    if (root == NULL || root->key == key)
        return root;

    if (root->key < key)
        return search(root->right, key);

    return search(root->left, key);
}
int main() {
    Node *root = NULL;
    root = insert(root, 5);
    root = insert(root, 3);
    root = insert(root, 8);
    root = insert(root, 6);
    root = insert(root, 4);
    root = insert(root, 2);
    root = insert(root, 1);
    root = insert(root, 7);
    cout << search(root, 5)->key << endl;
}

Complexity of BST insertion and search algorithms

Time Complexity

• Average situation

On average, the time complexity of inserting a node or searching for an element in a BST is comparable to the height of the binary search tree. On average, the height of a BST is O(logn). This is the case when the formed BST is a balanced BST. Therefore, the time complexity is [Big Theta]: O(logn).

• Best Case

In the best case, the tree is a balanced BST. The best case time complexity for insertion and search is O(logn). It is the same as the average case time complexity.

• Worst case scenario

In the worst case, we may have to traverse from the root node to the deepest leaf node, which is the entire height of the tree h. If the tree is unbalanced, that is, it is skewed, the height of the tree may become n, so the worst-case time complexity of insertion and search operations is O(n).

Space complexity

Due to the space required for the recursive calls, both the insertion and search operations have a space complexity of n O(n).