BinarySearchTree.swift

public class BinarySearchTree<T:Comparable>{
    private(set) public var value: T
    private(set) public var parent: BinarySearchTree<T>?
    private(set) public var leftChield: BinarySearchTree<T>?
    private(set) public var rightChield: BinarySearchTree<T>?
    
    public init(value: T){
        self.value = value
    }
    
    public convenience init(values: [T]){
        precondition(values.count>0)
        self.init(value: values.first!)
        for value in values.dropFirst(){
            insert(value)
        }
    }
    
    public var isRoot: Bool{
        return parent == nil ? true : false
    }
    
    public var isLeaf: Bool{
        return hasAnyChield ? false : true
    }
    
    public var isLeftChield: Bool{
        return parent?.leftChield?.value == value ? true : false
    }
    
    public var isRightChield: Bool{
        return parent?.rightChield?.value == value ? true : false
    }
    
    public var hasLeftChield: Bool{
        return self.leftChield != nil ? true : false
    }
    
    public var hasRightChield: Bool{
        return self.rightChield != nil ? true : false
    }
    
    public var hasAnyChield: Bool{
        return hasLeftChield || hasRightChield
    }
    
    public var hasBothChieldren: Bool{
        return hasLeftChield && hasRightChield
    }
    
    public var Count: Int{
        return (leftChield?.Count ?? 0) + 1 + (rightChield?.Count ?? 0)
    }
    
    public func insert(_ value: T){
        if value < self.value{
            if leftChield != nil{
                leftChield!.insert(value)
            }else{
                leftChield = BinarySearchTree(value: value)
                leftChield?.parent = self
            }
        }else if value > self.value{
            if rightChield != nil{
                rightChield?.insert(value)
            }else{
                rightChield = BinarySearchTree(value: value)
                rightChield?.parent = self
            }
        }
    }
    
    @discardableResult public func remove() -> BinarySearchTree?{
        let replacement: BinarySearchTree?
        
        if let right = rightChield{
            replacement = right.minumum()
        }else if let left = leftChield{
            replacement = left.maximum()
        }else{
            replacement = nil
        }
        
        replacement?.remove()
        
        replacement?.rightChield = rightChield
        replacement?.leftChield = leftChield
        leftChield?.parent = replacement
        rightChield?.parent = replacement
        reconnectToParentNode(node: replacement)
        
        // current node is no longer exist so
        parent = nil
        leftChield = nil
        rightChield = nil
        
        return replacement
    }
    
    private func reconnectToParentNode(node:BinarySearchTree?){
        if let parent = parent{
            if parent.isLeftChield{
                parent.leftChield = node
            }else{
                parent.rightChield = node
            }
        }
        node?.parent = parent
    }
    
    private func minumum() -> BinarySearchTree{
        var node = self
        while let next = node.leftChield{
            node = next
        }
        return node
    }
    
    private func maximum() -> BinarySearchTree{
        var node = self
        while let next = node.rightChield{
            node = next
        }
        return node
    }
    
    public func search(_ value: T) -> BinarySearchTree?{
        if value < self.value{
            return leftChield?.search(value)
        }else if value > self.value{
            return rightChield?.search(value)
        }else {
            return self
        }
    }
    
    public func traverseInOrder(_ process: (T) -> ()){
        leftChield?.traverseInOrder(process)
        process(value)
        rightChield?.traverseInOrder(process)
    }
    
    public func traversePreOrder(_ process: (T) -> ()){
        process(value)
        leftChield?.traversePreOrder(process)
        rightChield?.traversePreOrder(process)
    }
    
    public func travserPostOrder(_ process: (T) -> ()){
        leftChield?.travserPostOrder(process)
        rightChield?.travserPostOrder(process)
        process(value)
    }
    
    public func map<K>(_ formula: (T) -> K) -> [K]{
        var array = [K]()
        if let left = leftChield {
            array += left.map(formula)
        }
        array.append(formula(value))
        if let right = rightChield {
            array += right.map(formula)
        }
        return array
    }
    
    public func toArray() -> [T]{
        return map { $0 }
    }
    
    public var depth: Int{
        var node = self
        var edges = 0
        while let parent = node.parent{
            edges += 1
            node = parent
        }
        return edges
    }
    
    public var height:Int{
        if isLeaf{
            return 0
        }else{
            return 1 + max((leftChield?.height ?? 0), (rightChield?.height ?? 0))
        }
    }
    
    public func isBST(_ min: T, _ max: T) -> Bool{
        if  min > value || max < value { return false }
        let isLeftBST = leftChield?.isBST(min, value) ?? true
        let isRightBST = rightChield?.isBST(value, max) ?? true
        return isLeftBST && isRightBST
    }
}

extension BinarySearchTree: CustomStringConvertible{
    public var description: String{
        var s = ""
        if let left = leftChield{
            s += "\(left.description) <--"
        }
        s += " \(value) "
        if let right = rightChield{
            s += " --> \(right.description)"
        }
        return s
    }
}