A binary search tree is a data structure that stores information in a logical hierarchy.

A binary search tree is comprised of a key and two indicators. The key represents the data you would like to store, such as string or scalar value. Typically represented with pointers, the indicators store the location (also called the address) of its two children. The left child contains a value that is smaller than its parent. Conversely, the right child contains a value greater than its parent.

The same list (example below) visualized as a balanced BST. It does not matter that the values are unsorted. Rules governing the BST will place each node in its “correct” position accordingly.

Implementation below:

import Cocoa

/*
 A binary search tree is a data structure that stores information in a logical hierarchy.
 
 A binary search tree is comprised of a key and two indicators. The key represents
 the data you would like to store, such as string or scalar value. Typically represented with pointers,
 the indicators store the location (also called the address) of its two children.
 The left child contains a value that is smaller than its parent.
 Conversely, the right child contains a value greater than its parent.
 */


public class AVLTree <T: Comparable> {
    var key: T?
    var left: AVLTree?
    var right: AVLTree?
    
    var height: Int = 0
    
    // Add item
    func append(element key: T) {
        // Check root
        guard self.key != nil else {
            self.key = key
            self.height = 0
            return
        }
        
        // Check left side
        if key < self.key! {
            if self.left != nil {
                left?.append(element: key)
            } else {
                // New element
                let leftElement = AVLTree()
                leftElement.key = key
                leftElement.height = 0
                self.left = leftElement
            }
        }
        
        // Check right side
        if key > self.key! {
            if self.right != nil {
                right?.append(element: key)
            } else {
                // New element
                let rightElement = AVLTree()
                rightElement.key = key
                rightElement.height = 0
                self.right = rightElement
            }
        }
    }
}

// A simple array of unsorted integers
let numbers: Array<Int> = [8, 2, 10, 9, 11, 1, 7]

// Create a new BST instance
var root = AVLTree<Int>()

// Sort each item in the list
for number in numbers {
    root.append(element: number)
}

print(root)

<Example from Swift Algorithms & Data Structures by Wayne Bishop>