Skip to content

Instantly share code, notes, and snippets.

@aterribili
Last active May 13, 2017 13:33
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save aterribili/4602658e58d7e835ef540c5c2fe9a4ed to your computer and use it in GitHub Desktop.
Save aterribili/4602658e58d7e835ef540c5c2fe9a4ed to your computer and use it in GitHub Desktop.
BST in swift *Binary Search Tree*
enum BinarySearchTree<T: Comparable> {
case Leaf(T?)
indirect case Node(T, BinarySearchTree, BinarySearchTree)
}
func search<T: Comparable>(in tree: BinarySearchTree<T>, for item: T) -> Bool {
switch tree {
case .Leaf(let value):
return item == value
case .Node(let selfValue, let left, let right):
if selfValue > item {
return search(in: right, for: item)
}
return item == selfValue || search(in: left, for: item)
}
}
func insert<T: Comparable>(in tree: BinarySearchTree<T>, item: T) -> BinarySearchTree<T> {
switch tree {
case .Leaf(let value):
if let value = value {
if item > value {
return BinarySearchTree.Node(value, .Leaf(.none), .Leaf(item))
} else {
return BinarySearchTree.Node(value, .Leaf(item), .Leaf(.none))
}
}
return BinarySearchTree.Node(item, .Leaf(.none), .Leaf(.none))
case .Node(let value, let left, let right):
if item > value {
return BinarySearchTree.Node(value, left, insert(in: right, item: item))
} else if item < value {
return BinarySearchTree.Node(value, insert(in: left, item: item), right)
} else {
return BinarySearchTree.Node(value, left, right)
}
}
}
BinarySearchTree.Node(10, .Leaf(.none), .Leaf(.none))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment