// helper 
public class BinaryNode<Element> {
    
    public var value: Element
    public var leftChild: BinaryNode?
    public var rightChild: BinaryNode?
    
    public init(value: Element) {
        self.value = value
    }
}

extension BinaryNode: CustomStringConvertible {
    
    public var description: String {
        return diagram(for: self)
    }
    
    private func diagram(for node: BinaryNode?,
                         _ top: String = "",
                         _ root: String = "",
                         _ bottom: String = "") -> String {
        guard let node = node else {
            return root + "nil\n"
        }
        if node.leftChild == nil && node.rightChild == nil {
            return root + "\(node.value)\n"
        }
        return diagram(for: node.rightChild, top + " ", top + "┌──", top + "│ ")
            + root + "\(node.value)\n"
            + diagram(for: node.leftChild, bottom + "│ ", bottom + "└──", bottom + " ")
    }
}

extension BinaryNode {
    
    public func traverseInOrder(visit: (Element) -> Void) {
        leftChild?.traverseInOrder(visit: visit)
        visit(value)
        rightChild?.traverseInOrder(visit: visit)
    }
    
    public func traversePreOrder(visit: (Element) -> Void) {
        visit(value)
        leftChild?.traversePreOrder(visit: visit)
        rightChild?.traversePreOrder(visit: visit)
    }
    
    public func traversePostOrder(visit: (Element) -> Void) {
        leftChild?.traversePostOrder(visit: visit)
        rightChild?.traversePostOrder(visit: visit)
        visit(value)
    }
}

// 1
public struct BinarySearchTree<Element: Comparable> {
  public private(set) var root: BinaryNode<Element>?
  public init() {}
}

// 2
extension BinarySearchTree: CustomStringConvertible {
  public var description: String {
    return root?.description ?? "empty tree"
  }
}

extension BinarySearchTree {
    /**
     해당 함수는 사용자 인터페이스로 공개되는 함수이고, 내부적으로는 다른 함수의 재귀적인 실행에 의해서 값이 추가 됩니다.
     */
    public mutating func insert(_ value: Element) {
        root = insert(from: root, value: value)
        
    }
    private mutating func insert(from node: BinaryNode<Element>?, value: Element) -> BinaryNode<Element> {
        // root에 값이 없는 경우에 값을 추가한 경우에는 root의 값을 추가한다.
        // 혹은 아래의 if, else 구문에서 left,right 자식 노드에 추가될때 호출됨.
        guard let node = node else { return BinaryNode<Element>(value: value)}
        
        // 추가한 값이, 해당 node의 값보다 작으면 해당 노드의 왼쪽 자식 노드에
        if value < node.value {
            node.leftChild = insert(from: node.leftChild, value: value)
        } else {
            node.rightChild = insert(from: node.rightChild, value: value)
        }
        return node
    }

// 2
example(of: "building a BST") {
  var bst = BinarySearchTree<Int>()
  for i in 0..<5 {
    bst.insert(i)
  }
print(bst) 
}

// 1
public func contains(_ value: Element) -> Bool {
  // 1
  var current = root
  // 2
  while let node = current {
// 3
    if node.value == value {
return true
}
// 4
    if value < node.value {
      current = node.leftChild
} else {
      current = node.rightChild
    }
}
return false
}

// 2
example(of: "finding a node") {
  if exampleTree.contains(5) {
    print("Found 5!")
  } else {
    print("Couldn't find 5")
  }
}

// 1
private extension BinaryNode {
    // 재귀적으로 해당 노드를 기준으로 가장 작은값 반환, 만약 nil 이라면, 현재의 자기 자신 노드 반환
    var min: BinaryNode {
        return leftChild?.min ?? self
    }
}

// 2
extension BinarySearchTree {
    public mutating func remove(_ value: Element) {
        root = remove(node: root, value: value)
    }
    private mutating func remove(node: BinaryNode<Element>?, value: Element) -> BinaryNode<Element>? {
        guard let node = node else { return nil }
        /**
         1. 지우려고 하는 값이, 현재 node의 값과 같은 경우
            - 여기에서 지울수 있는 케이스가 3가지가 나옴
         2. 지우려고 하는 값이, 현재 node의 값보다 작은 경우
            - 현재 node의 왼쪽 자식 노드로 remove 재귀적으로 실행
         3. 지우려고 하는 값이, 현재 node의 값보다 큰 경우
            - 현재 node의 오른쪽 자식 노드로 remove 재귀적으로 실행
         */
        if value == node.value {
            if node.leftChild == nil && node.rightChild == nil { return nil }
            if node.leftChild == nil { return node.rightChild }
            if node.rightChild == nil { return node.leftChild }
            node.value = node.rightChild!.min.value
            node.rightChild = remove(node: node.rightChild, value: node.value)
        }else if value < node.value {
            node.leftChild = remove(node: node.leftChild, value: value)
        }else {
            node.rightChild = remove(node: node.rightChild, value: value)
        }
        return node
    }
}

// 3
example(of: "removing a node") {
  var tree = exampleTree
  print("Tree before removal:")
  print(tree)
  tree.remove(3)
  print("Tree after removing root:")
  print(tree)
}