ThrowingInorder.swift

import Foundation

func testIsBST() {
    let list = [2, -10, -45, 200, 48, 10, 38, 47, 4, 2, 5]
    var tree = BinaryTree<Int>(2)
    for i in list[1...] {
        tree.insert(i)
    }
    
    let test = isBST(tree)
    XCTAssertFalse(test, tree.description)
}

func isBST(_ binaryTree: BinaryTree<Int>) -> Bool {
    
    var prev: Int = Int.min
    do {
        try binaryTree.inorderTraversal { value in
            guard value >= prev else {
                throw BinarySearchTree<Int>.Error.unsorted
            }
            prev = value
        }
    } catch {
        return false
    }
    
    return true
}

open class BinaryTree<T>: CustomStringConvertible where T: Comparable {
    var value: T
    var left: BinaryTree<T>? = nil
    var right: BinaryTree<T>? = nil
    
    public init(_ value: T) {
        self.value = value
    }
    
    open func insert(_ newValue: T) {
        switch (left, right) {
            case (.none, .some(_)):
                left = BinaryTree(newValue)
            case (.some(_), .none):
                right = BinaryTree(newValue)
            case let (.some(l), .some(r)):
                if Bool.random() {
                    l.insert(newValue)
                } else {
                    r.insert(newValue)
                }
            case (.none, .none):
                if Bool.random() {
                    left = BinaryTree(newValue)
                } else {
                    right = BinaryTree(newValue)
                }
        }
    }
    
    open func contains(_ value: T) -> Bool {
        preconditionFailure("not implemented")
    }
    
    open func inorderTraversal<U>(_ action: (T) throws -> U) throws {
        try left?.inorderTraversal(action)
        try action(value)
        try right?.inorderTraversal(action)
    }
    
    open var description: String {
        var values: [T] = []
        try? inorderTraversal {
            values.append($0)
        }
        return values.map({ String(describing: $0) }).joined(separator: ", ")
    }
}

open class BinarySearchTree<T>: BinaryTree where T: Comparable {}

public extension BinarySearchTree {
    enum Error: Swift.Error {
        case unsorted
    }
}