Binary Search Tree Implementation in Swift

1. Introduction

A Binary Search Tree (BST) is a tree data structure in which each node has at most two children, referred to as the left child and the right child. For each node, all elements in the left subtree are less than the node, and all elements in the right subtree are greater than the node. This ensures a fast lookup, addition, and deletion of items from the tree.

2. Implementation Steps

1. Define a Node class to represent each element in the BST. This class will contain a value, a left child, and a right child.

2. Create the BinarySearchTree class.

3. Implement methods to insert nodes.

4. Implement methods to search for a value.

5. Implement methods to delete nodes.

6. Implement a method to print the BST.

3. Implementation in Swift

class Node<T: Comparable> {              // 1. Node class
    var value: T
    var leftChild: Node?
    var rightChild: Node?
    init(value: T) {
        self.value = value
    }
}
class BinarySearchTree<T: Comparable> {
    var root: Node<T>?
    // 3. Insert node
    func insert(value: T) {
        root = insert(from: root, with: value)
    }
    private func insert(from node: Node<T>?, with value: T) -> Node<T> {
        guard let node = node else {
            return Node(value: value)
        }
        if value < node.value {
            node.leftChild = insert(from: node.leftChild, with: value)
        } else if value > node.value {
            node.rightChild = insert(from: node.rightChild, with: value)
        }
        return node
    }
    // 4. Search for a value
    func search(value: T) -> Bool {
        return search(from: root, for: value)
    }
    private func search(from node: Node<T>?, for value: T) -> Bool {
        guard let node = node else {
            return false
        }
        if value == node.value {
            return true
        } else if value < node.value {
            return search(from: node.leftChild, for: value)
        } else {
            return search(from: node.rightChild, for: value)
        }
    }
    // Note: Deletion method is more involved and not included in this basic implementation.
    // 6. Print BST
    func printTree() {
        inOrderTraversal(from: root)
    }
    private func inOrderTraversal(from node: Node<T>?) {
        guard let node = node else { return }
        inOrderTraversal(from: node.leftChild)
        print(node.value)
        inOrderTraversal(from: node.rightChild)
    }
}
// Usage:
let bst = BinarySearchTree<Int>()
bst.insert(value: 5)
bst.insert(value: 2)
bst.insert(value: 8)
bst.insert(value: 1)
bst.insert(value: 3)
bst.printTree()   // Outputs: 1, 2, 3, 5, 8
print(bst.search(value: 4)) // Outputs: false

Output:

1
2
3
5
8
false

Explanation:

1. The Node class represents each element in the Binary Search Tree. It contains a value and pointers to left and right children.

2. The BinarySearchTree class manages the overall tree and operations on it.

3. The insert method adds a node to the BST, maintaining the BST property of left nodes being less than the current node and right nodes being greater.

4. The search method checks if a given value is present in the BST.

5. Deletion in a BST can be complex due to the need to maintain the BST property, so a basic implementation is not shown in this post.

6. The printTree method uses in-order traversal to print nodes of the BST in ascending order.