Transform a sorted array to a balanced BST. Cracking_Problem 4.2 on page 109

SortedArrayToBST.swift

import Foundation

//-------------Basic BST Operation-------------------
class Node
{
  var key: Int?
  var left: Node?
  var right: Node?
  
  var description: String {
    guard let value = key else { return "NAN" }
    return "Node: \(value)"
  }
}

// Insert a key into BST with root node
func Insert(_ key: Int, root: Node)
{
  
  let newNode = Node()
  newNode.key = key
  
  var node: Node? = root
  var lastNode: Node? = root
  while (node != nil) {
    guard let value = node?.key else { break }
    if (value < key) {
      lastNode = node
      node = node?.right
      if (node == nil) {
        lastNode?.right = newNode
      }
    }
    else {
      lastNode = node
      node = node?.left
      if (node == nil) {
        lastNode?.left = newNode
      }
    }
  }
  
}

func InorderTraversal(_ root: Node?)
{
  if (root == nil) { return }
  
  InorderTraversal(root!.left)
  if (nil != root!.key) { print(root!.key!) }
  InorderTraversal(root!.right)
}

func LevelTraversal(_ root: Node?, traverse: (Int,Int)->())
{
  guard let root = root else { return }
  
  var nodeArray: Array<Node> = []
  var levelArray: Array<Int> = []
  nodeArray.append(root)
  levelArray.append(0)
  
  while(nodeArray.count > 0) {
    guard let node = nodeArray.first, let level = levelArray.first else {
      continue
    }
    nodeArray.remove(at: 0)
    levelArray.remove(at:0)
    traverse(node.key!, level)
    
    if (node.left != nil) {
      nodeArray.append(node.left!)
      levelArray.append(level + 1)
    }
    
    if (node.right != nil) {
      nodeArray.append(node.right!)
      levelArray.append(level + 1)
    }
    
  }
}

//----------Sorted Array to BST Solution---------------

let sortedArray = [1, 2, 3, 4 ,5 , 6, 7, 8 ,9 , 10]

func SortedToBST(_ sorted: Array<Int>, begin: Int, end: Int, root: Node)
{  
  assert(end < sorted.count, "The end index is out of range in input array")
  
  if (begin > end) { return }
  
  if (begin == end || 1 == sorted.count) {
    Insert(sortedArray[begin], root: root)
    return
  }
  
  let mid = (begin + end) / 2
  
  if (nil == root.key) {
    root.key = sortedArray[mid]
  }
  else { 
      Insert(sortedArray[mid], root: root)
  }
  
  SortedToBST(sorted, begin: begin, end: mid - 1, root: root)
  SortedToBST(sorted, begin: mid + 1, end: end, root: root)
  
}

let root = Node()
SortedToBST(sortedArray, begin: 0, end: sortedArray.count - 1, root: root)

InorderTraversal(root)

print("------------------------")
print("Start LevelTraversal...")
LevelTraversal(root) { (key, level) in
  print("Node: \(key), level: \(level)")
}