Binary Tree

BinaryTree.swift

// Code inside modules can be shared between pages and other source files.

public class BinaryNode {
    public var val: Int
    public var left: BinaryNode?
    public var right: BinaryNode?
    public init() { self.val = 0
        self.left = nil
        self.right = nil
    }
    public init(_ val: Int) { 
        self.val = val
        self.left = nil
        self.right = nil
    }
    public init(_ val: Int, _ left: BinaryNode?, _ right: BinaryNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
    
    // Traverse tree and return a block handler for each node. 
    func inOrder(_ root: BinaryNode?, nodeHandler: (BinaryNode?) -> ()) {
        if let left = root?.left {
            inOrder(left) { node in
                nodeHandler(node)
            }            
        }
        nodeHandler(root)
        
        if let right = root?.right { 
            inOrder(right) { node in 
                nodeHandler(node)
            }
        }
    }
}

// https://www.objc.io/books/optimizing-collections/
extension BinaryNode: CustomStringConvertible {
    
    public var description: String {
        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.left == nil && node.right == nil {
            return root + "\(node.val)\n"
        }
        return diagram(for: node.right, top + " ", top + "┌──", top + "│ ")
            + root + "\(node.val)\n"
            + diagram(for: node.left, bottom + "│ ", bottom + "└──", bottom + " ")
    }
}

public func sortedArrayToBST(_ nums: [Int?]) -> BinaryNode? {
    let compact = nums.compactMap { $0 }
    return sortedArrayToBST(compact, leftIndex: 0, rightIndex: compact.count - 1)
    
    func sortedArrayToBST(_ arr: [Int], leftIndex: Int, rightIndex: Int) -> BinaryNode? {
        guard rightIndex >= leftIndex else {
            return nil
        }
        
        let mid = leftIndex + (rightIndex - leftIndex) / 2

        let root = BinaryNode(arr[mid])
        root.left = sortedArrayToBST(arr, leftIndex: leftIndex, rightIndex: mid - 1) 
        root.right = sortedArrayToBST(arr, leftIndex: mid + 1, rightIndex: rightIndex)
        
        return root
    }
}

let tree = sortedArrayToBST([1,2,5,6,7,8,23,55])

print(tree!)

/*

  ┌──55
 ┌──23
 │ └──nil
┌──8
│ └──7
6
│ ┌──5
└──2
 └──1

*/