Following on from my last post, this is a short post with code samples to achieve the above on Swift. I won’t talk too much about the background to Binary Search Trees or the BFS algorithm, instead just focus on the code. If you need to get more of a background to this post, then best have a read of my previous post, Breadth-First Search in Typescript and Javascript.
The code
Just like my previous post, this code solves the exact same problem, except here it’s done in Swift instead of Typescript or Javascript.
class Node<T: Comparable> {
var key: T!
var left: Node?
var right: Node?
init(key:T) {
self.key = key
}
}
class Queue<T> {
private var items = [T]()
func add(item: T) {
items.append(item)
}
func pop() -> T? {
return items.removeFirst()
}
func isEmpty() -> Bool {
return (items.count == 0)
}
}
class BinaryTree<H:Comparable> {
private var rootNode: Node<H>?
func setRoot(node: Node<H> ) {
self.rootNode = node
}
func addNode(key: H) {
rootNode = addNodeByReursion(currentNode: rootNode, key: key)
}
func addNodeByReursion(currentNode: Node<H>?, key: H) -> Node<H>? {
if let cNode = currentNode {
if key < cNode.key {
cNode.left = addNodeByReursion(currentNode: cNode.left, key: key)
} else if key > cNode.key {
cNode.right = addNodeByReursion(currentNode: cNode.right, key: key)
}
} else {
return Node<H>(key: key)
}
return currentNode
}
func levelOrderTraversal(from: Int?) {
//for this purpose, let's ignore from
if let rn = rootNode {
let nodeQueue:Queue<Node<H>> = Queue<Node<H>>()
nodeQueue.add(item: rn)
while !nodeQueue.isEmpty() {
let cNode = nodeQueue.pop()!
print(cNode.key ?? "")
if let left = cNode.left {
nodeQueue.add(item: left)
}
if let right = cNode.right {
nodeQueue.add(item:right)
}
}
} else {
return
}
}
}
let tree = BinaryTree<Int>()
tree.addNode(key: 7)
tree.addNode(key: 8)
tree.addNode(key: 4)
tree.addNode(key: 3)
tree.levelOrderTraversal(from: nil)
Like the previous version, we have 3 classes to create a Queue, Node and BinaryTree.
You can copy and paste all this code into your Xcode playground to run it. When you run it, you will see the numbers at each level .printed to console starting from the root.
I can’t quite tell, why I feel the Typescript version is better to look at? could it be because it reminds me of modern Java and Java is first love? i.e. first programming language that I worked with when starting out and the language I have the most experience with.
As usual, if you find any of my posts useful support us by buying or even trying one of our products and leave us a review on the app store.
Comments