Mastering the Binary Search Tree (BST): Creation, Traversal

Introduction

Binary Search Tree, Traversal, Insertion, Deletion, sorting

Binary search tree, traversal — inorder, preorder, postorder, insertion, deletion, and sorting,

A Binary Search Tree (BST) is a vital data structure in computer science, offering efficient methods to organize, search, and manipulate data. With its unique structure and properties, BST ensures quick lookups, insertions, and deletions while maintaining data in sorted order. This guide provides an overview of key BST operations, including binary search tree, traversal — inorder, preorder, postorder, insertion, deletion, and sorting, with examples to illustrate each concept.

Table of Contents

Key Features of a Binary Search Tree

A BST organizes nodes based on these properties:

Binary Search Key: All keys in the left subtree of a node are smaller than the node’s key, and all keys in the right subtree are larger.
Recursive Structure: Both left and right subtrees are themselves BSTs.
Efficient Search: The structure ensures operations like searching, insertion, and deletion have a time complexity of O(h)O(h)O(h), where hhh is the tree’s height.

What is a Binary Search Tree?

A Binary Search Tree is a binary tree where:

The left subtree of a node contains values less than the node’s key.
The right subtree of a node contains values greater than the node’s key.
Both left and right subtrees must themselves be binary search trees.

This unique property makes BSTs highly efficient for searching, insertion, and deletion operations.

Key Operations on a Binary Search Tree

1. Traversal

Traversal refers to visiting all nodes of the tree in a specific order. Common traversal methods include:

Inorder Traversal (Left → Root → Right)
This traversal produces sorted order in a BST.
Preorder Traversal (Root → Left → Right)
Used for creating a copy of the tree.
Postorder Traversal (Left → Right → Root)
Useful for deleting or evaluating the tree.

Example of Inorder Traversal:

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

def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.key, end=" ")
        inorder_traversal(root.right)

# Example Tree
root = Node(50)
root.left = Node(30)
root.right = Node(70)
root.left.left = Node(20)
root.left.right = Node(40)
root.right.left = Node(60)
root.right.right = Node(80)

inorder_traversal(root)
# Output: 20 30 40 50 60 70 80

2. Insertion

Insertion in a BST involves placing a new key in its correct position to maintain the BST property.

Example of Insertion:

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

# Insert new values into the tree
root = None
root = insert(root, 50)
insert(root, 30)
insert(root, 70)
insert(root, 20)
insert(root, 40)
insert(root, 60)
insert(root, 80)
inorder_traversal(root)
# Output: 20 30 40 50 60 70 80

3. Search

Searching involves finding a key in the BST. The time complexity for this operation is O(h)O(h), where hh is the height of the tree.

Example of Search:

def search(root, key):
    if root is None or root.key == key:
        return root
    if key < root.key:
        return search(root.left, key)
    return search(root.right, key)

# Search for a value
result = search(root, 40)
print("Found" if result else "Not Found")
# Output: Found

4. Deletion

Deletion in a BST is slightly complex because we need to ensure the tree’s structure remains intact. There are three cases to consider:

Node to be deleted is a leaf: Remove it directly.
Node to be deleted has one child: Replace the node with its child.
Node to be deleted has two children: Replace the node with its in-order successor (smallest value in the right subtree).

Example of Deletion:

def min_value_node(node):
    current = node
    while current.left:
        current = current.left
    return current

def delete_node(root, key):
    if root is None:
        return root
    if key < root.key:
        root.left = delete_node(root.left, key)
    elif key > root.key:
        root.right = delete_node(root.right, key)
    else:
        # Node with one child or no child
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        # Node with two children
        temp = min_value_node(root.right)
        root.key = temp.key
        root.right = delete_node(root.right, temp.key)
    return root

# Deleting a value
root = delete_node(root, 50)
inorder_traversal(root)
# Output: 20 30 40 60 70 80

5. Sorting with BST

Sorting using a BST is simply an inorder traversal. This property makes BSTs useful for applications requiring sorted outputs.

Example of Sorting:
Insert elements into the BST and perform an inorder traversal:

nums = [40, 10, 50, 20, 30]
root = None
for num in nums:
    root = insert(root, num)

print("Sorted Order:")
inorder_traversal(root)
# Output: 10 20 30 40 50

Advantages of Using BSTs

Efficient Searching: O(h)O(h) complexity ensures fast lookup.
Dynamic Updates: Insertions and deletions maintain sorted order dynamically.
Sorted Outputs: Inorder traversal inherently provides sorted data.

Conclusion

Binary Search Trees are a powerful tool for managing and organizing data. By mastering traversal, insertion, deletion, and sorting, you can unlock the full potential of BSTs for a wide range of applications, including search engines, databases, and hierarchical data storage.

Explore BSTs, practice the operations, and harness their efficiency in your projects!

Name: Subir Chakraborty

Phone Number: +91-9135005108

Email ID: teamemancipation@gmail.com

Our Platforms:

Digilearn Cloud

EEPL Test

Live Emancipation

Instagram – EEPL Classroom