binarySearchTree.swift

public class BinarySearchTree<T: Comparable> {
  private(set) public var value: T
  private(set) public var parent: BinarySearchTree?
  private(set) public var left: BinarySearchTree?
  private(set) public var right: BinarySearchTree?

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

  public var isRoot: Bool {
    return parent == nil
  }

  public var isLeaf: Bool {
    return left == nil && right == nil
  }

  public var isLeftChild: Bool {
    return parent?.left === self
  }

  public var isRightChild: Bool {
    return parent?.right === self
  }

  public var hasLeftChild: Bool {
    return left != nil
  }

  public var hasRightChild: Bool {
    return right != nil
  }

  public var hasAnyChild: Bool {
    return hasLeftChild || hasRightChild
  }

  public var hasBothChildren: Bool {
    return hasLeftChild && hasRightChild
  }

  public var count: Int {
    return (left?.count ?? 0) + 1 + (right?.count ?? 0)
  }
  
  
  public func insert(value: T) {
    insert(value: value, parent: self)
  }

  private func insert(value: T, parent: BinarySearchTree) {
    if value < self.value {
      if let left = left {
        left.insert(value: value, parent: left)
      } else {
        left = BinarySearchTree(value: value)
        left?.parent = parent
      }
    } else {
      if let right = right {
        right.insert(value: value, parent: right)
      } else {
        right = BinarySearchTree(value: value)
        right?.parent = parent
      }
    }
  }
  
  public func search(value: T) -> BinarySearchTree? {
    if value < self.value {
      return left?.search(value: value)
    } else if value > self.value {
      return right?.search(value: value)
    } else {
      return self  // found it!
    }
  }
  
   public func maximum() -> BinarySearchTree {
    var node = self
    while case let next? = node.right {
      node = next
    }
    return node
  }
  
  
  
   public func minimum() -> BinarySearchTree {
    var node = self
    while case let next? = node.left {
      node = next
    }
    return node
  }
  
  
  public func predecessor() -> BinarySearchTree {
    if let left = left {
        return left.maximum()
    } else {
        var node = self 
        while case let parent = node.parent {
            if value > parent.value {
                return parent
            }    
            node = parent 
        }
        return nil
    }
    
    
    
  
  
  }
  
}
extension BinarySearchTree: CustomStringConvertible {
  public var description: String {
    var s = ""
    if let left = left {
      s += "(\(left.description)) <- "
    }
    s += "\(value)"
    if let right = right {
      s += " -> (\(right.description))"
    }
    return s
  }
}

let tree = BinarySearchTree<Int>(value: 5)
tree.insert(value: 2)
tree.insert(value: 6)
tree.insert(value: 3)
tree.insert(value: -10)
print(tree.predecessor())
print(tree.search(value: 2))
print(tree)