Swift Xcode implementation of InterviewCake _Super Balanced Tree_ using a tight DFS in a `BinaryTreeNode` extension. ⚠️ Spoiler alert: this is an actual answer to the https://www.interviewcake.com/question/swift/balanced-binary-tree question, so no peeking!

InterviewCake-BinaryTreeNode.swift

//
//  BinaryTreeNode.swift
//

import Foundation

class BinaryTreeNode {

    var value: Int
    var left: BinaryTreeNode?
    var right: BinaryTreeNode?

    init(_ value: Int) {
        self.value = value
    }

    func insert(leftValue: Int) -> BinaryTreeNode {
        let left = BinaryTreeNode(leftValue)
        self.left = left
        return left
    }

    func insert(rightValue: Int) -> BinaryTreeNode {
        let right = BinaryTreeNode(rightValue)
        self.right = right
        return right
    }
}

InterviewCake-SuperBalanced.swift

//
//  SuperBalanced.swift
//
//  Copyright © 2018 Xavier Schott
//  Permission is hereby granted, free of charge, to any person obtaining a copy
//  of this software and associated documentation files (the "Software"), to deal
//  in the Software without restriction, including without limitation the rights
//  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
//  copies of the Software, and to permit persons to whom the Software is
//  furnished to do so, subject to the following conditions:
//
//  The above copyright notice and this permission notice shall be included in
//  all copies or substantial portions of the Software.
//
//  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
//  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
//  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
//  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
//  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
//  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
//  THE SOFTWARE.
//

import Foundation

extension BinaryTreeNode {
    private func visitDFS(depth: Int, minDepth: inout Int, maxDepth: inout Int ) {
        if maxDepth - minDepth < 2 {            // Short circuit
            maxDepth = max(maxDepth, depth)     // Any node will increase depth
            if nil == left && nil == right {    // Leaf
                minDepth = min(minDepth, depth) // Shallowest leaf
            } else {                            // Node, keep going
                left?.visitDFS(depth: depth + 1, minDepth: &minDepth, maxDepth: &maxDepth)
                right?.visitDFS(depth: depth + 1, minDepth: &minDepth, maxDepth: &maxDepth)
            }
        }
    }
    
    func superBalanced() -> Bool {
        var minDepth = Int.max
        var maxDepth = 0
        
        visitDFS(depth: 0, minDepth: &minDepth, maxDepth: &maxDepth)
        return maxDepth - minDepth < 2
    }
}

InterviewCake-uperBalancedTests.swift

//
//  SuperBalancedTests.swift
//
//  Copyright © 2018 Xavier Schott
//  Permission is hereby granted, free of charge, to any person obtaining a copy
//  of this software and associated documentation files (the "Software"), to deal
//  in the Software without restriction, including without limitation the rights
//  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
//  copies of the Software, and to permit persons to whom the Software is
//  furnished to do so, subject to the following conditions:
//
//  The above copyright notice and this permission notice shall be included in
//  all copies or substantial portions of the Software.
//
//  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
//  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
//  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
//  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
//  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
//  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
//  THE SOFTWARE.
//

import XCTest

class SuperBalancedTests: XCTestCase {
    func testBalancedTree() {
        let node0 = BinaryTreeNode(0)

        let node1 = BinaryTreeNode(1)
        node0.left = node1
        let node2 = BinaryTreeNode(2)
        node0.right = node2

        let node5 = BinaryTreeNode(5)
        node2.left = node5
        let  node6 = BinaryTreeNode(6)
        node2.right = node6

        XCTAssertTrue(node0.superBalanced())
    }

    func testSmallGoodRightTrees() {
        let node0 = BinaryTreeNode(0)
        XCTAssertTrue(node0.superBalanced())

        let node2 = BinaryTreeNode(2)
        node0.right = node2
        XCTAssertTrue(node0.superBalanced())

        let  node6 = BinaryTreeNode(6)
        node2.right = node6
        XCTAssertTrue(node0.superBalanced())

        let node14 = BinaryTreeNode(14)
        node6.right = node14
        XCTAssertTrue(node0.superBalanced())
}

    func testSmallGoodLefttTrees() {
        let node0 = BinaryTreeNode(0)
        XCTAssertTrue(node0.superBalanced())

        let node1 = BinaryTreeNode(1)
        node0.left = node1
        XCTAssertTrue(node0.superBalanced())

        let  node3 = BinaryTreeNode(3)
        node1.left = node3
        XCTAssertTrue(node0.superBalanced())

        let node7 = BinaryTreeNode(7)
        node3.left = node7
        XCTAssertTrue(node0.superBalanced())
    }

    func testSingleBranchTrees() {
        let node0 = BinaryTreeNode(0)
        let node2 = BinaryTreeNode(2)
        node0.right = node2
        let  node6 = BinaryTreeNode(6)
        node2.right = node6
        let node14 = BinaryTreeNode(14)
        node6.right = node14
        XCTAssertTrue(node0.superBalanced())

        let node1 = BinaryTreeNode(1)
        node0.left = node1
        XCTAssertFalse(node0.superBalanced())
    }

    func testImbalancedBalancedTree() {
        let node0 = BinaryTreeNode(0)

        let node1 = BinaryTreeNode(1)
        node0.left = node1
        let node2 = BinaryTreeNode(2)
        node0.right = node2

        let node5 = BinaryTreeNode(5)
        node2.left = node5
        let  node6 = BinaryTreeNode(6)
        node2.right = node6

        let node9 = BinaryTreeNode(9)
        node5.left = node9

        XCTAssertFalse(node0.superBalanced())
    }

    func testPerformanceExample() {
        // This is an example of a performance test case.
        self.measure {
            // Put the code you want to measure the time of here.
        }
    }
}

Using a very short recursive DFS, combined with a shortcut exit.

This routines stops when nodes are too deep, not even looking for further leaves.