This is a practice code for BST written in Swift

BST_Practice.swift

import Foundation

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

func find(_ key: Int, root: Node?) -> Node?
{
  if root == nil { return root }
  
  var nextNode = root
  
  while (nextNode != nil) {
    
    if let value = nextNode?.key, key < value  {
      nextNode = nextNode?.left
    }
    else if let value = nextNode?.key, value < key {
      nextNode = nextNode?.right
    }
    else {
      break
    }
  }
  
  return nextNode
}

// 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) {
        newNode.parent = lastNode
        lastNode?.right = newNode
      }
    }
    else {
      lastNode = node
      node = node?.left
      if (node == nil) {
        newNode.parent = lastNode
        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)
    }
    
  }
}

func min(_ root: Node?) -> Node?
{
  if (root == nil) { return root }
  
  var next: Node? = root
  while (next?.left != nil) {
    next = next?.left
  }
  
  return next
}

func minR(_ root: Node?) -> Node?
{
  if (root == nil || root?.left == nil) { return root }
  return minR(root?.left)
}

func max(_ root: Node?) -> Node?
{
  if (root == nil) { return root }
  
  var next: Node? = root
  while (next?.right != nil) {
    next = next?.right
  }
  
  return next
}

func maxR(_ root: Node?) -> Node?
{
  if (root == nil || root?.right == nil) { return root }
  return maxR(root?.right)
}

func successor(of node: Node?) -> Node?
{
  if (node == nil) { return node }
  
  var current = node
  if let right = current?.right {
      return min(right)   
  }

  var parent = current?.parent
  while (true) {
    if let currentValue = current?.key, 
        let leftValue = parent?.left?.key,
        currentValue != leftValue 
    {
        current = parent
        parent = parent?.parent
    }
    else {
      break
    }
  }
  
  return parent  
}

func predecessor(of node: Node?) -> Node?
{
  if (node == nil) { return node }
  
  var current = node
  if let left = current?.left {
    return max(left)
  }
  
  var parent = current?.parent
  while (true) {
    if let currentValue = current?.key, 
        let leftValue = parent?.left?.key,
        currentValue == leftValue 
    {
        current = parent
        parent = parent?.parent
    }
    else {
      break
    }
  }

  return parent
}