A Binary Search Tree implementation in Swift

BinarySearchTree.swift

//: Playground - noun: a place where people can play
// Inspiration: http://cslibrary.stanford.edu/110/BinaryTrees.html

import UIKit

var values = [10, 5, 6, 8, 9, 22, 3, 2, 4, 7, 14]

class Node {
    var value:Int = 0
    var left:Node? = nil
    var right:Node? = nil
    init(value:Int, left:Node?, right:Node?) {
      self.value = value
      self.left = left
      self.right = right
    }
}

class BinarySearchTree {
  var root:Node? = nil
    
  init(values:[Int]) {
    values.forEach { value in
      root = insertRecursive(node: root, value: value)
    }
  }
    
  // MARK:- Private helpers
  
  // Recursive method that inserts a value at a given node and create a Binary Search Tree
  private func insertRecursive(node:Node?, value:Int) -> Node? {
    guard let node = node else {
      // node is nil,
      return Node(value: value, left: nil, right: nil)
    }
    
    // Recur down the tree
    if (value <= node.value) {
      node.left = insertRecursive(node: node.left, value: value)
    } else {
      node.right = insertRecursive(node: node.right, value: value)
    }
    
    return node
  }
  
  private func lookUpRecursive(node: Node?, value:Int) -> Bool {
    guard let node = node else {
      return false
    }
    
    if node.value == value {
      return true
    }
    
    // Pick the correct tree to recur through
    if (value < node.value) {
      // Go left, son!
      return lookUpRecursive(node: node.left, value: value)
    } else {
      // Go right!
      return lookUpRecursive(node: node.right, value: value)
    }
  }
  
  private func BST(node:Node?) -> Bool {
    guard let node = node else {
      // This could still be a BST if node is nil
      return true
    }
        
    guard let leftNode = node.left, let rightNode = node.right else {
      // node w/ no children
      return true
    }
        
    // Check the failure case of the current node and children
    if leftNode.value > node.value && rightNode.value <= node.value {
      return false
    }
      
    // Otherwise keep going
    return BST(node: node.left) && BST(node: node.right)
  }
    
  private func countNodes(node:Node?) -> Int {
    guard let node = node else {
      // no node here...
      return 1
    }

    // Go all the way left..
    let leftCount = countNodes(node: node.left)
    let rightCount = countNodes(node: node.right)

    return leftCount + rightCount
  }
    
  private func simplePrint(node:Node?) -> String {
    guard let node = node else {
      return ""
    }

    return "\(simplePrint(node: node.left)) \(String(node.value)) \(simplePrint(node: node.right))"
  }
    
  private func simplePostorderPrint(node:Node?) -> String {
    guard let node = node else {
      return ""
    }
    
    return simplePrint(node: node.left) + " " + simplePrint(node: node.right) + " [" + String(node.value) + "]"
  }
    
  private func prettyPrint(node:Node?, path: inout [Int]) -> String {
    guard let node = node else {
      return ""
    }
    return String(node.value)
  }

    
  // MARK:- Public functions
  
  func insert(value: Int) {
    root = insertRecursive(node: root, value: value)
  }
  
  func lookUp(value: Int) -> Bool {
    return lookUpRecursive(node: root, value: value);
  }

  func size() -> Int {
    guard let root = root else {
      return 0
    }
        
    return countNodes(node: root) - 1 // don't count the root node
  }
  
  // This is a bit redundant if we ensure that our insert function inserts
  // in such a way that we create a BST by default.
  func isBST() -> Bool {
    return BST(node: root)
  }
  
  // Recurs over the tree and prints each node's value going left-to-right.
  func printTree() {
    print(simplePrint(node: root))
  }
    
  func printPostorderTree() {
    print(simplePostorderPrint(node: root))
  }
}



// Playin' around:
let tree = BinarySearchTree(values: values)
//tree.size()
//tree.isBST()
tree.printTree()
tree.lookUp(value: 77)

//tree.printPostorderTree()
//tree.prettyPrintTree()

//let reverseTree = buildReverseBinaryTree(values: values)
//reverseTree.size()
//reverseTree.isBST()
//reverseTree.printTree()


//tree.foo()



// Test insert
//tree.insert(value: 100)
//tree.printTree()
//
//tree.insert(value: 0)
//tree.printTree()
//
//tree.insert(value: 100)
//tree.printTree()
//
//tree.insert(value: 1)
//tree.printTree()




// Junk:
// Recursive method that inserts a value in reverse order...
//func reverseInsert(node:Node?, value:Int) -> Node? {
//    guard let node = node else {
//        // node is nil,
//        return Node(value: value, left: nil, right: nil)
//    }
//
//    // Recur down the tree
//    if (value >= node.value) {
//        node.left = insert(node: node.left, value: value)
//    } else {
//        node.right = insert(node: node.right, value: value)
//    }
//
//    return node
//}

// Probably a fancier way to do this as well...
//func buildReverseBinaryTree(values:[Int]) -> BinarySearchTree {
//    var root:Node? = nil
//    values.forEach { (value:Int) in
//        root = reverseInsert(node: root, value: value)
//    }
//    return BinarySearchTree(root: root)
//}

// Overflows the stack by eventually running out of memory
// while attempting to allocate space for infinitely calling foo.
//func foo() {
//  return foo()
//}


//  func prettyPrintTree() {
//    var path:[Int] = []
//    print(prettyPrint(node: root, path: &path))
//  }
//

//    TO DO:
//    func maxDepth() -> Int {
//
//    }
//
//    func minValue() -> Int {
//    }