Binary Search Tree

A Binary Search Tree (BST) is a type of non-linear data structure that is used to store data in a sorted manner. It is a special type of binary tree where each node contains a value, and the values are arranged according to a specific rule.

In a Binary Search Tree, each node can have a maximum of two children. These two children are called the left child and right child. The main purpose of creating a BST is to make searching, insertion, and deletion operations faster compared to linear data structures such as arrays and linked lists.

The important property of a Binary Search Tree is:

• All values present in the left subtree of a node are smaller than the value of that node.
• All values present in the right subtree of a node are greater than the value of that node.
• The left and right subtrees must also follow the same rule.

For example, consider the following Binary Search Tree:

                 50
               /    \
             30      70
            /  \    /  \
          20   40 60   80

In this tree:

• Nodes 20, 30, and 40 are smaller than 50, so they are placed in the left subtree.
• Nodes 60, 70, and 80 are greater than 50, so they are placed in the right subtree.

Because every node follows this rule, the given tree is a valid Binary Search Tree.

What is a Binary Search Tree?

A Binary Search Tree is a binary tree with an additional ordering property that allows efficient searching.

A normal binary tree only defines that a node can have at most two children.

Example of a normal binary tree:

              10
            /    \
           5      20
          / \
         30  2

There is no restriction on where values are placed.

However, in a Binary Search Tree, the placement of values follows a fixed order.

Example:

              50
            /    \
          30      70
         /  \    /  \
       20   40 60   80

Here: Left subtree < Root node < Right subtree

This ordering property allows the BST to perform searching efficiently.

Structure of a Binary Search Tree Node

Each node of a Binary Search Tree contains three parts:

        Node

+---------------------+
| Left | Data | Right |
+---------------------+

Where:

• Data: Stores the value of the node.
• Left Pointer: Stores the address of the left child.
• Right Pointer: Stores the address of the right child.

For example:

              50
            /    \
          30      70

The node representation will be:

Node 50

Data = 50

Left pointer  → Address of node 30

Right pointer → Address of node 70

If a node does not have a child, the corresponding pointer contains NULL.

Example:

          50
         /
       30

Representation:

Node 50

Data = 50

Left pointer → Address of 30

Right pointer → NULL

Characteristics of Binary Search Tree

A Binary Search Tree has the following characteristics:

1. Each Node Has Maximum Two Children

A binary tree allows each node to have at most two children:

• Left child
• Right child

Example:

              50
             /  \
           30    70

The node 50 has two children, 30 and 70.

2. Values in Left Subtree are Smaller

For every node, all values in the left subtree are smaller than the node value.

Example:

              50
             /
           30
          /
        20

Here: 20 < 30 < 50

Therefore, the left subtree property is satisfied.

3. Values in Right Subtree are Greater

For every node, all values in the right subtree are greater than the node value.

Example:

        50
          \
           70
             \
              90

Here: 50 < 70 < 90

Therefore, the right subtree property is satisfied.

Creating a Binary Search Tree

A Binary Search Tree is created by inserting elements one by one.

During insertion, every new value is compared with the root node:

• If the value is smaller, it moves to the left subtree.
• If the value is greater, it moves to the right subtree.
• The process continues until an empty position is found.

Consider inserting these values:

50, 30, 70, 20, 40, 60, 80

Step 1: Insert 50

The tree is empty, so 50 becomes the root.

        50

Step 2: Insert 30

Compare 30 with 50.

30 < 50

Therefore, 30 is placed on the left side.

          50
         /
       30

Step 3: Insert 70

Compare 70 with 50.

70 > 50

Therefore, 70 is placed on the right side.

          50
         /  \
       30    70

Step 4: Insert 20

• Compare: 20 < 50
• Move left. 20 < 30
• Move left again.

Insert 20.

              50
             /  \
           30    70
          /
        20

Step 5: Insert 40

• Compare: 40 < 50
• Move left. 40 > 30
• Move right.

Insert 40.

              50
             /  \
           30    70
          / \
        20  40

After inserting all values:

                 50
               /    \
             30      70
            /  \    /  \
          20   40 60   80

This is the final Binary Search Tree.

Searching in Binary Search Tree

Searching is one of the most important operations performed on a BST.

The BST property helps us decide whether we should search in the left subtree or the right subtree.

Suppose we want to search for 60.

Given tree:

                 50
               /    \
             30      70
                    /
                  60

Step 1

Compare 60 with root node 50.

60 > 50

Move to the right subtree.

Step 2

Compare 60 with 70.

60 < 70

Move to the left subtree.

Step 3

60 is found.

Element Found

The search process avoids checking unnecessary nodes.

Searching Algorithm

Search(root, key)

1. If root is NULL
       return NOT FOUND

2. If key == root.data
       return FOUND

3. If key < root.data
       Search left subtree

4. Else
       Search right subtree

Time Complexity of Searching

The efficiency of searching depends on the height of the BST.

Insertion Operation in Binary Search Tree

Insertion is the process of adding a new node into an existing Binary Search Tree while maintaining the BST property.

When inserting a new value:

• First, compare the new value with the root node.
• If the new value is smaller than the root, move to the left subtree.
• If the new value is greater than the root, move to the right subtree.
• Continue this process until an empty position is found.
• Insert the new node at that position.

The insertion operation always places a new node at the leaf position of the tree.

Example of BST Insertion

Consider the following Binary Search Tree:

                 50
               /    \
             30      70
            /  \    /  \
          20   40 60   80

Now, suppose we want to insert the value 65.

Step 1: Compare with Root Node

The root node is 50.

Compare:

65 > 50

Since 65 is greater than 50, we move to the right subtree.

                 50
                   \
                    70

Step 2: Compare with Node 70

Now compare 65 with 70.

65 < 70

Since 65 is smaller than 70, move to the left subtree.

                 70
                /
              60

Step 3: Compare with Node 60

Compare 65 with 60.

65 > 60

Move to the right side of 60.

The right position is empty, so insert 65.

Final BST:

                 50
               /    \
             30      70
            /  \    /  \
          20   40 60   80
                    \
                     65

The BST property is still maintained:

Left subtree < Node < Right subtree

Algorithm for Insertion in BST

Insert(root, key)

1. If root is NULL:
       Create a new node
       Return the new node

2. If key < root.data:
       Insert key into left subtree

3. Else if key > root.data:
       Insert key into right subtree

4. Return root

Deletion Operation in Binary Search Tree

Deletion is one of the most complex operations in a Binary Search Tree.

When deleting a node, we must ensure that the remaining tree still satisfies the BST property.

There are three possible cases when deleting a node:

1. Deleting a leaf node
2. Deleting a node with one child
3. Deleting a node with two children

Case 1: Deleting a Leaf Node

A leaf node is a node that does not have any child.

Example:

             50
            /  \
          30    70
         /
       20

Here, node 20 is a leaf node.

Suppose we delete 20.

Before deletion:

             50
            /  \
          30    70
         /
       20

After deletion:

             50
            /  \
          30    70

Since 20 has no children, it can simply be removed.

Case 2: Deleting a Node with One Child

A node may have only one child.

Example:

              50
             /
           30
             \
              40

Suppose we delete node 30.

Node 30 has one child:

40

The child replaces the deleted node.

After deletion:

              50
             /
           40

The BST property remains unchanged.

Case 3: Deleting a Node with Two Children

This is the most complicated deletion case.

Consider the following BST:

                 50
               /    \
             30      70
                    /  \
                  60    80

Suppose we want to delete node 70.

Node 70 has two children:

• Left child = 60
• Right child = 80

To delete it:

1. Find the inorder successor (smallest in right sub-tree) or inorder predecessor (largest in left sub-tree).
2. Replace the deleted node value with the successor value.
3. Delete the original successor node.

Finding Inorder Successor

The inorder successor is the smallest value in the right subtree.

Right subtree of 70:

80

Smallest value:

80

Replace 70 with 80.

Before:

                 50
               /    \
             30      70
                    /  \
                  60    80

After replacing:

                 50
               /    \
             30      80
                    /
                  60

Now the original 80 node is removed.

Final tree:

                 50
               /    \
             30      80
                    /
                  60

Algorithm for Deletion in BST

Delete(root, key)

1. If root is NULL:
       return NULL

2. If key < root.data:
       Delete from left subtree

3. Else if key > root.data:
       Delete from right subtree

4. Else:
       Node found

       Case 1:
       Node has no child
       Remove node

       Case 2:
       Node has one child
       Replace node with child

       Case 3:
       Node has two children
       Replace with inorder successor

5. Return root

Traversal of Binary Search Tree

Traversal means visiting all nodes of a tree exactly once.

Unlike linear data structures, trees can be traversed in different ways.

The main traversal techniques are:

1. Inorder Traversal
2. Preorder Traversal
3. Postorder Traversal
4. Level Order Traversal

Consider this BST:

                 50
               /    \
             30      70
            /  \    /  \
          20   40 60   80

1. Inorder Traversal

The inorder traversal of a BST always gives elements in sorted order.

Inorder traversal follows:

Left → Root → Right

Steps:

Visit left subtree:

20 30 40

Visit root:

50

Visit right subtree:

60 70 80

Final output:

20 30 40 50 60 70 80

Algorithm for Inorder Traversal

Inorder(root)

1. If root is not NULL

2. Traverse left subtree

3. Visit root node

4. Traverse right subtree

2. Preorder Traversal

Preorder follows:

Root → Left → Right

For the same BST:

                 50
               /    \
             30      70
            /  \    /  \
          20   40 60   80

Traversal:

First visit root:

50

Then left subtree:

30 20 40

Then right subtree:

70 60 80

Output:

50 30 20 40 70 60 80

Applications of Preorder Traversal

Preorder traversal is useful for:

• Creating a copy of a tree
• Storing tree structure
• Expression tree evaluation

3. Postorder Traversal

Postorder follows:

Left → Right → Root

For the same tree:

Left subtree:

20 40 30

Right subtree:

60 80 70

Root:

50

Output:

20 40 30 60 80 70 50

Applications of Postorder Traversal

Used in:

• Deleting complete trees
• Memory deallocation
• Calculating directory sizes

4. Level Order Traversal

Level order traversal visits nodes level by level.

It uses a queue data structure.

Example:

                 50
               /    \
             30      70
            /  \    /  \
          20   40 60   80

Traversal:

Level 1:

50

Level 2:

30 70

Level 3:

20 40 60 80

Output:

50 30 70 20 40 60 80

Finding Minimum and Maximum Value in Binary Search Tree

One of the important advantages of a Binary Search Tree is that finding the smallest and largest element is very efficient.

Because of the ordering property of BST:

• The smallest value is always present at the leftmost node.
• The largest value is always present at the rightmost node.

Consider the following Binary Search Tree:

                 50
               /    \
             30      70
            /  \    /  \
          20   40 60   80

Finding Minimum Value in BST

To find the minimum value:

1. Start from the root node.
2. Move continuously to the left child.
3. The node where the left child becomes NULL is the minimum value.

Example:

Start from root:

                 50
                /
              30
             /
           20

Path:

50 → 30 → 20

Node 20 has no left child.

Therefore:

Minimum Value = 20

Algorithm to Find Minimum Value

FindMin(root)

1. If root is NULL:
       Tree is empty

2. While root.left is not NULL:
       Move to left child

3. Return root.data

Finding Maximum Value in BST

To find the maximum value:

1. Start from the root node.
2. Move continuously to the right child.
3. The node where the right child becomes NULL is the maximum value.

Example:

                 50
                   \
                    70
                      \
                       80

Path: 50 → 70 → 80

Node 80 has no right child.

Therefore:

Maximum Value = 80

Algorithm to Find Maximum Value

FindMax(root)

1. If root is NULL:
       Tree is empty

2. While root.right is not NULL:
       Move to right child

3. Return root.data

Height of Binary Search Tree

The height of a Binary Search Tree is the number of edges present in the longest path from the root node to the leaf node.

It represents the maximum number of levels that must be traversed to reach any node.

Consider the following tree:

              50
             /
           30
          /
        20

The longest path is: 50 → 30 → 20

Number of edges:

50 to 30 = 1 edge

30 to 20 = 1 edge

Therefore:

Height = 2

Height Formula

The height of a node can be calculated as:

Height(Node) = 1 + Maximum(Height(left subtree), Height(right subtree))

For an empty tree:

Height(NULL) = -1

For a tree containing only one node:

Height = 0

Example of Height Calculation

Consider:

                 50
               /    \
             30      70
            /        /
          20       60
         /
       10

Left side height:

50 → 30 → 20 → 10

Edges:

3

Right side height:

50 → 70 → 60

Edges:

2

Therefore:

Height of BST = Maximum(3,2)

Height = 3

Time Complexity Analysis of Binary Search Tree

The performance of BST operations depends on the height of the tree.

Let:

n = number of nodes
h = height of tree

Most operations depend on the height:

Time Complexity = O(h)

Complexity Table

Why Worst Case is O(n)?

The worst case occurs when the BST becomes a skewed tree.

Example:

Insert:

10,20,30,40,50

Tree:

10
 \
 20
   \
    30
      \
       40
         \
          50

Searching for 50:

Comparisons:

10 → 20 → 30 → 40 → 50

Number of comparisons: 5

For n nodes: 

Comparisons = n

Therefore:

Worst Case Complexity = O(n)

Applications of Binary Search Tree

Binary Search Trees are widely used in computer science because they provide efficient searching and sorting capabilities.

1. Searching Applications

BST provides faster searching compared to linear data structures.

Example:

Searching employee records:

Employee ID → Employee Information

A BST can quickly locate records based on the employee ID.

2. Database Indexing

Databases use tree-based indexing structures to efficiently search and retrieve records.

For example:

Searching a student record:

Roll Number → Student Details

3. Implementing Sets and Maps

Many programming languages use balanced versions of BST for implementing:

• Sets
• Dictionaries
• Maps

Examples:

Key → Value

4. Symbol Tables in Compilers

Compilers use tree structures to store information about:

• Variables
• Functions
• Identifiers

Example:

Variable Name → Memory Location

5. Sorting Data

Since inorder traversal of BST gives sorted output, BST can be used for sorting.

Example:

Insert:

50,30,70,20,40

BST:

              50
            /    \
          30      70
         /  \
       20   40

Inorder traversal:

20 30 40 50 70

Sorted data is obtained automatically.

Advantages of Binary Search Tree

1. Efficient Searching

Searching is faster compared to arrays and linked lists when the tree is balanced.

Average complexity: O(log n)

2. Dynamic Size

Unlike arrays, BST does not require fixed memory allocation.

Nodes can be added or removed dynamically.

3. Maintains Sorted Data

BST automatically maintains data in sorted order.

Inorder traversal provides sorted elements.

4. Efficient Insertion and Deletion

Insertion and deletion are easier compared to sorted arrays because shifting elements is not required.

Disadvantages of Binary Search Tree

1. Can Become Skewed

A BST can lose efficiency if elements are inserted in sorted order.

Example:

10
 \
 20
   \
    30

2. Extra Memory Requirement

Each node requires additional memory for storing pointers.

A node stores:

Data
Left Pointer
Right Pointer

3. Performance Depends on Structure

A balanced BST performs efficiently, but an unbalanced BST performs poorly.

Binary Search Tree vs Binary Tree

Numerical Questions for Student Practice

Question 1: BST Construction and Traversal Insert the following elements in the given order: 50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24.

• Draw the resulting BST.
• List the inorder, preorder, and postorder traversals.
• Identify the minimum and maximum elements.

Question 2: Deletion and Height Given the sequence: 25, 15, 10, 22, 35, 30, 70, 90, 45.

• Construct the BST.
• What is the height of this tree?
• Delete the node 35 and draw the updated tree.

Question 3: Ancestry and Successors Construct a BST from: 50, 70, 60, 20, 90, 10, 40, 100.

• Find the inorder successor of node 60.
• Find the lowest common ancestor (LCA) of nodes 62 and 75 (Note: Assume these values were to be searched/inserted).

Question 4: Comprehensive Analysis Create a BST using: 100, 80, 120, 70, 90, 110, 130.

• Perform all four traversals (Inorder, Preorder, Postorder, Level-order).
• Search for the value 95 and describe the steps taken.

Question 5: Root Deletion Starting with a BST containing: 40, 20, 60, 10, 30, 50, 70.

• Delete the root node 40.
• Redraw the tree and verify if it remains a valid BST.

Summary

A Binary Search Tree (BST) is a special type of binary tree that stores elements in an ordered manner. Each node follows the rule that values smaller than the node are stored in the left subtree and values greater than the node are stored in the right subtree.

Because of this property, BST provides efficient searching, insertion, and deletion operations. The average time complexity of these operations is O(log n) when the tree is balanced. However, if the tree becomes skewed, the performance can degrade to O(n).

BST is widely used in applications such as database indexing, searching systems, symbol tables, and implementing sets and maps.

Understanding Binary Search Trees is an important foundation for advanced tree structures such as:

• AVL Trees
• Red-Black Trees
• B-Trees
• Binary Heaps