A generic AVL tree with SequenceType, CollectionType and ArrayLiteralConvertible extensions

I'm learning Swift and trying get a good understanding of some of its many features. The following is an AVL tree implementation with extensions that conform to SequenceType, CollectionType and ArrayLiteralConvertible

Everything seems to work correctly. I wish to get some feedback on my overall approach, pointers on how I can improve it and conventions I should be following.

```
protocol BinarySearchTreeType {
associatedtype Element
mutating func insert(element: Element)
mutating func find(element: Element) -> Element?
}

class Node {
var value: Element
var leftNode: Node?
var rightNode: Node?

init(value: Element) {
self.value = value
}

var height: Int {
let left = leftNode != nil ? leftNode!.height + 1 : 0
let right = rightNode != nil ? rightNode!.height + 1: 0
return max(left, right)
}
}

enum BinarySearchTreeError: ErrorType {
case OutOfBound
}

final class BinarySearchTree: BinarySearchTreeType {

private var _root: Node?
private var _count: Int = 0

var root: Node? {
return _root
}
var count: Int {
return _count
}

/**
Inserts an element into the AVL tree. Duplicate elements are ignored.
- parameter element: Element which will be added to the tree.
It must conform to Comparable.
*/
func insert (element: Element) {
if let _ = _root {
self.insert(element, currentNode: &_root!)
} else {
_root = Node(value: element)
_count += 1
}
}

private func insert(element: Element, inout currentNode: Node) -> Node {
if currentNode.value > element {
if currentNode.leftNode != nil {
currentNode.leftNode = insert(element, currentNode: ¤tNode.leftNode!)
} else {
currentNode.leftNode = Node(value: element)
_count += 1
}
if height(currentNode.leftNode) - height(currentNode.rightNode) == 2 {
if element (value: element)
_count += 1
}

if height(currentNode.rightNode) - height(currentNode.le

I have a major point of criticism regarding the "Swifty-ness" of your code:
There is far too much "forced unwrapping" of optionals, and explicit comparing against nil.
This can almost always be avoided by using

• Optional binding: if/while let myValue = myOptional { ... },

• optional chaining: myOptional?.property, or

• the nil-coalescing operator: myOptional ?? defaultValue.

See also When should I compare an optional value to nil?
on Stack Overflow.

Example 1:

func minNode(root: Node) -> Node {
    var _current = root
    while _current.leftNode != nil {
        _current = _current.leftNode!
    }
    return _current
}

should be written with optional binding as

func minNode(root: Node) -> Node {
    var _current = root
    while let lNode = _current.leftNode {
        _current = lNode
    }
    return _current
}

It is even shorter because
the leftNode property is accessed only once per loop iteration.

Example 2:

private func height (node: Node?) -> Int {
    return node != nil ? node!.height : -1
}

can be simplified with optional chaining and the nil-coalescing operator ??:

private func height (node: Node?) -> Int {
    return node?.height ?? -1
}

Example 3:

func insert(element: Element) {
    if let _ = _root {
        self.insert(element, currentNode: &_root!)
    } else {
        _root = Node(value: element)
        _count += 1
    }
}

Again forced unwrapping, and if let _ = _root is just if _root != nil in disguise.
The above transformations do not work directly in this case
because self.insert(element, currentNode: &_root!) modifies the last argument.

But actually the

private func insert(element: Element, inout currentNode: Node) -> Node {
    // ...
    return currentNode
}

does not really need an inout parameter because it returns the new root of the
tree after the insertion. It can be rewritten as

private func insert(element: Element, currentNode: Node) -> Node {
    var currentNode = currentNode // make mutable copy
    // ... 
    return currentNode
}

And now the insert(element: Element) method can use optional binding as well:

func insert(element: Element) {
    if let node = _root {
        _root = self.insert(element, currentNode: node)
    } else {
        _root = Node(value: element)
        count += 1
    }
}

The same principle can be applied at many places in your code. I hope that the above
examples can serve as a starting point to clean-up the handling of optionals.

The "public readonly, private read-write" properties "root" and "count" can be
defined as

private(set) var root: Node?
private(set) var count: Int = 0

which makes the additional accessor methods obsolete. Actually root need not be
publicly visible at all.

The value property of Node should be declared as a constant because modifying
the value makes no sense after a node as been inserted in the tree.

My suggestion would be to fix the "optional handling" first and then review the code in a second iteration.

StackExchange Code Review Q#133349, answer score: 4