BST
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123
class BinaryNode<Element>{
var value: Element
var leftNode: BinaryNode?
var rightNode: BinaryNode?
init(_ value: Element) {
self.value = value
}
//left is minimum, if not available then self is minimum
var min:BinaryNode? {
return leftNode?.min ?? self
}
public func minimum() -> BinaryNode {
var node = self
while let next = node.leftNode {
node = next
}
return node
}
public func maximum() -> BinaryNode {
var node = self
while let next = node.rightNode {
node = next
}
return node
}
}
// This is for display purposes ONLY!!!
extension BinaryNode: CustomStringConvertible {
public var description: String {
var s = ""
if let left = leftNode {
s += "(\(left.description)) <- "
}
s += "\(value)"
if let right = rightNode {
s += " -> (\(right.description))"
}
return s
}
}
extension BinarySearchTree:CustomStringConvertible {
var description: String {
guard let root = root else {
return "Empty Tree"
}
return String(describing:root)
}
}
struct BinarySearchTree<Element:Comparable> {
private(set) var root:BinaryNode<Element>?
init() { }
mutating func insert(_ value: Element) -> BinarySearchTree{
let newNode = BinaryNode(value)
if root == nil {
root = newNode
return self
} else {
guard let root = root else {
return self
}
var currentNode = root
while true {
if value < currentNode.value {
//check left node
if currentNode.leftNode == nil {
currentNode.leftNode = newNode
return self
} else {
currentNode = currentNode.leftNode! //force-casting is fine in this case because we already done nil check
}
} else {
if value == currentNode.value {
fatalError("duplicates are not allowed in BST")
}
//check right node
if currentNode.rightNode == nil {
currentNode.rightNode = newNode
return self
} else {
currentNode = currentNode.rightNode!
}
}
}
}
return self
}
///Check if value is available in a BST
func lookup(_ value: Element) -> Bool {
return false
}
///Remove a value from BST
func remove(_ value:Element) -> Bool {
return false
}
}
var bst = BinarySearchTree<Int>()
bst.insert(9)
bst.insert(4)
bst.insert(6)
bst.insert(20)
bst.insert(170)
bst.insert(15)
bst.insert(1)
print(bst)
Swift
INFO