Binary tree implementation using Swift enum

Question

I'm doing some experiments with Swift enums to become more familiarized with them and have implemented a rudimentary binary tree. It works when adding up to three items, but adding more beyond that doesn't change it and I couldn't see why it wasn't working.

Here's the code:

protocol TreeProtocol {
    mutating func insert(value: Int)
    func walk()
}


enum Tree:TreeProtocol {
    case Empty
    case Leaf(Int)
    case Node(Int, TreeProtocol?, TreeProtocol?)

    init(){
        self = .Empty;
    }

    init(value: Int) {
        self = .Leaf(value)
    }

    init(value: Int, left:TreeProtocol?, right:TreeProtocol?){
        self = .Node(value, left, right);
    }

    mutating func insert(value: Int) {
        switch self {
        case .Empty:
            self = .Leaf(value)

        case .Leaf(let currentNodeValue):
            let newTree = Tree(value: value) // var here generates a warning
            if value < currentNodeValue {
                self = .Node(currentNodeValue, newTree, .None)
            }
            else {
                self = .Node(currentNodeValue, .None, newTree)
            }

        case let .Node(currentNodeValue, leftNode, rightNode):
            if (value < currentNodeValue) {
                if leftNode == nil {
                    let newTree = Tree(value: value)
                    self = .Node(currentNodeValue, newTree, rightNode)
                }
                else {
                    var l = leftNode! // unable to call leftNode!.insert() directly
                    l.insert(value)
                }
            }
            else {
                if rightNode == nil {
                    let newTree = Tree(value: value)
                    self = .Node(currentNodeValue, leftNode, newTree)
                }
                else {
                    var r = rightNode!
                    r.insert(value)
                }
            }
        }
    }

    func walk() {
        switch self {
        case .Empty:
            print("Empty")
        case .Leaf (let value):
            print("\(value), ")
        case .Node(let value, let leftNode, let rightNode):
            if leftNode != nil {
                leftNode!.walk()
            }
            print("\(value) ")
            if (rightNode != nil) {
                rightNode!.walk()
            }
        }
    }
}

And if I run the following tests:

    var tree = Tree();
    tree.walk()

    tree.insert(100)
    tree.walk()

    tree.insert(50)
    tree.walk()

    tree.insert(150)
    tree.walk()

    tree.insert(25)
    tree.walk()

The output is:

    Empty

    100

    50,
    100

    50,
    100,
    150

    50,
    100,
    150

The 25 value is not getting added to the tree

(This code is a bit inelegant, its just the first iteration, there's several ugly parts in there that could be improved and beautified. Waiting for recursive enum functionality to be added to the Xcode beta).

Answer 1

Because you're mutating the internal nodes and that is actually creating a copy of them. That copy is never inserted into the tree, it's just thrown away after being modified. If after inserting into l and r you reinsert those nodes (with self = .Node(currentNodeValue, l, rightNode) and self = .Node(currentNodeValue, leftNode, r) respectively) then the tree as a whole will get updated. It's a by-value / by-reference issue.

Answer 2

I know you already have an answer, but I really like your implementation and thought I'd provide the code for implementing @Wain's solution and also streamline some of the nested if-else logic.

It involves a slight modification for the protocol, so that insert returns a value:

protocol TreeProtocol {
    mutating func insert(value: Int) -> TreeProtocol
    func walk()
}

And then the insert function can be rewritten like this:

mutating func insert(value: Int) -> TreeProtocol {
    switch self {
    case .Empty:
        self = .Leaf(value)

    case .Leaf(let currentNodeValue):
        let newTree = Tree(value: value)
        self = value < currentNodeValue
            ? .Node(currentNodeValue, newTree, .None)
            : .Node(currentNodeValue, .None, newTree)

    case var .Node(currentNodeValue, leftNode, rightNode):
        self = value < currentNodeValue
            ? .Node(currentNodeValue, leftNode?.insert(value) ?? Tree(value: value), rightNode)
            : .Node(currentNodeValue, leftNode, rightNode?.insert(value) ?? Tree(value: value))
    }
    return self
}