BST

Overview

A Binary Search Tree (BST) is a binary tree where each node contains a key, and it satisfies the following property:

• All keys in the left subtree are less than the node’s key.

• All keys in the right subtree are greater than the node’s key.

This structure allows efficient searching, insertion, and deletion operations.

Key Operations and Their Time Complexity

Swift Implementation of a BST

Node Definition

class BSTNode<T: Comparable> {
    var value: T
    var left: BSTNode?
    var right: BSTNode?

    init(value: T) {
        self.value = value
    }
}

BST Class

class BinarySearchTree<T: Comparable> {
    private(set) var root: BSTNode<T>?

    func insert(_ value: T) {
        root = insert(from: root, value: value)
    }

    private func insert(from node: BSTNode<T>?, value: T) -> BSTNode<T> {
        guard let node = node else {
            return BSTNode(value: value)
        }

        if value < node.value {
            node.left = insert(from: node.left, value: value)
        } else {
            node.right = insert(from: node.right, value: value)
        }

        return node
    }

    func contains(_ value: T) -> Bool {
        var current = root
        while let node = current {
            if value == node.value {
                return true
            } else if value < node.value {
                current = node.left
            } else {
                current = node.right
            }
        }
        return false
    }

    func inOrderTraversal(_ visit: (T) -> Void) {
        inOrderTraversal(from: root, visit: visit)
    }

    private func inOrderTraversal(from node: BSTNode<T>?, visit: (T) -> Void) {
        guard let node = node else { return }
        inOrderTraversal(from: node.left, visit: visit)
        visit(node.value)
        inOrderTraversal(from: node.right, visit: visit)
    }

    func remove(_ value: T) {
        root = remove(from: root, value: value)
    }

    private func remove(from node: BSTNode<T>?, value: T) -> BSTNode<T>? {
        guard let node = node else { return nil }

        if value < node.value {
            node.left = remove(from: node.left, value: value)
        } else if value > node.value {
            node.right = remove(from: node.right, value: value)
        } else {
            if node.left == nil && node.right == nil {
                return nil
            } else if node.left == nil {
                return node.right
            } else if node.right == nil {
                return node.left
            } else {
                if let minLargerNode = findMin(from: node.right) {
                    node.value = minLargerNode.value
                    node.right = remove(from: node.right, value: minLargerNode.value)
                }
            }
        }

        return node
    }

    private func findMin(from node: BSTNode<T>?) -> BSTNode<T>? {
        var current = node
        while let next = current?.left {
            current = next
        }
        return current
    }
}

Example Usage

let bst = BinarySearchTree<Int>()
bst.insert(50)
bst.insert(30)
bst.insert(70)
bst.insert(20)
bst.insert(40)
bst.insert(60)
bst.insert(80)

print("In-order traversal:")
bst.inOrderTraversal { print($0) }

print("Contains 40: \(bst.contains(40))")
print("Contains 100: \(bst.contains(100))")

bst.remove(70)
print("In-order traversal after deleting 70:")
bst.inOrderTraversal { print($0) }

Visual Example

For the values inserted in the example:

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

After removing 70, it becomes:

        50
       /  \
     30    80
    /  \   /
   20  40 60

Summary

A Binary Search Tree is a foundational structure for implementing efficient lookup and ordered data operations. However, it can degrade to a linked list in worst-case scenarios (e.g., inserting sorted data). For self-balancing behavior, explore AVL trees or Red-Black Trees in subsequent chapters.