// Самый глубокий элемент в дереве

// 1 способ
// Найти высоту данного дерева, а затем напечатать узел на самом нижнем уровне

func height(_ root: Node?) -> Int {
    if root == nil {
        return 0
    }
    return max(height(root!.left), height(root!.right)) + 1
}

func execute(_ root: Node?) -> Int? {

    let levels = height(root)
    var deepest: Int?

    func deepestNode(_ root: Node?, _ levels: Int) {
        if root == nil {
            return
        }
        if levels == 1 {
            deepest = root!.value
        } else if levels > 1 {
            deepestNode(root!.left, levels - 1)
            deepestNode(root!.right, levels - 1)
        }
    }
    deepestNode(root, levels)
    return deepest
}



// 2 способ

func deepestNode(_ root: TreeNode?) -> Int {
    guard let root = root else {
        return 0
    }

    var q = [TreeNode]()
    q.append(root)
    var node: TreeNode?

    while !q.isEmpty {
        node = q.removeFirst()
        if let left = node?.left {
            q.append(left)
        }
        if let right = node?.right {
            q.append(right)
        }
    }

    return node!.data
}