Skip to content

Instantly share code, notes, and snippets.

@aterribili

aterribili/bst.swift

Last active May 13, 2017
Embed
What would you like to do?
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