DSA Binary Search Trees (BST)

Welcome to TheCodingCollege.com! In this guide, we will explore the concept of Binary Search Trees (BSTs), their properties, operations, and applications in Data Structures and Algorithms (DSA). Understanding BSTs is essential for solving problems involving dynamic data storage and efficient searching.

What is a Binary Search Tree (BST)?

A Binary Search Tree is a specialized binary tree where each node follows a specific ordering property:

  • For any node, all values in its left subtree are less than the node’s value.
  • All values in its right subtree are greater than the node’s value.

This property ensures efficient operations like searching, insertion, and deletion.

Properties of a Binary Search Tree

  1. Binary Tree: Each node has at most two children.
  2. Ordering Rule: Left subtree values < Node value < Right subtree values.
  3. Unique Values: BSTs generally store unique elements.

Basic Operations in BST

  1. Insertion: Add a new value while maintaining the BST property.
  2. Searching: Find whether a value exists in the tree.
  3. Deletion: Remove a value and restructure the tree to preserve the BST property.
  4. Traversal: Visit all nodes in a specific order (In-order, Pre-order, Post-order).

Why Use a Binary Search Tree?

  1. Efficient Searching: Searching in a balanced BST takes O(log n) time.
  2. Dynamic Data Structure: Supports dynamic insertion and deletion.
  3. Foundation for Advanced Structures: BSTs are the basis for structures like AVL trees and Red-Black trees.

Binary Search Tree Implementation

Node Class

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

Insertion in BST

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

# Example Usage
root = None
root = insert(root, 10)
root = insert(root, 5)
root = insert(root, 15)
root = insert(root, 7)

Search in BST

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

# Example Usage
found = search(root, 7)
print("Found!" if found else "Not Found!")  # Output: Found!

Deletion in BST

  1. Locate the node to delete.
  2. Handle three cases:
    • Node has no children (leaf node).
    • Node has one child.
    • Node has two children (replace with in-order successor or predecessor).
def delete(root, key):
    if root is None:
        return root
    if key < root.value:
        root.left = delete(root.left, key)
    elif key > root.value:
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        successor = find_min(root.right)
        root.value = successor.value
        root.right = delete(root.right, successor.value)
    return root

def find_min(node):
    while node.left is not None:
        node = node.left
    return node

# Example Usage
root = delete(root, 7)

Traversals in BST

In-order Traversal

  • Left → Root → Right
  • Produces a sorted sequence of elements.
def inorder(root):
    if root:
        inorder(root.left)
        print(root.value, end=" ")
        inorder(root.right)

# Output: 5 7 10 15

Time and Space Complexity

OperationBest Case (Balanced)Worst Case (Skewed)
SearchO(log n)O(n)
InsertO(log n)O(n)
DeleteO(log n)O(n)
TraversalO(n)O(n)

Applications of Binary Search Trees

  1. Efficient Searching: BSTs allow for O(log n) searches in balanced scenarios.
  2. Dynamic Sets: Suitable for maintaining dynamic sets of ordered data.
  3. Database Indexing: BSTs form the basis for indexing in databases.
  4. Priority Queues: BSTs can be adapted for priority queue implementations.

Common BST Problems

  1. Construct a BST from a sorted array.
  2. Check if a tree is a valid BST.
  3. Find the kth smallest or largest element in a BST.
  4. Convert a BST to a balanced binary search tree.

Practice Problem

Problem: Given the following sequence of numbers, construct a binary search tree and perform in-order traversal:
[10, 5, 20, 3, 7, 15, 30]

Solution:

  1. Construct the BST using the insertion algorithm.
  2. Perform in-order traversal: 3 → 5 → 7 → 10 → 15 → 20 → 30

Conclusion

Binary Search Trees (BSTs) are a fundamental concept in DSA. Their efficient operations make them an excellent choice for dynamic data storage and retrieval. Understanding their implementation and operations will solidify your foundation in data structures.

Leave a Comment