Binary Tree Using Swift Enum

Question

I am doing some experiments with Swift enums to make them more familiar with them and implement a rudimentary binary tree. It works when adding up to three elements, but adding more than that does not change it, and I could not understand why it does not work.

Here is 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() 

Conclusion:

  Empty 100 50, 100 50, 100, 150 50, 100, 150 

Value 25 is not added to the tree.

(This code is a little inelegant, it's just the first iteration, there are a few ugly parts that can be improved and decorated). Waiting for a recursive enumeration function to be added to the beta version of Xcode).

Answer 1

I know that you already have an answer, but I really like your implementation, and I would think of providing code for implementing the @Wain solution, as well as optimizing some of the nested logical if-else .

It includes a slight protocol modification, so insert returns a value:

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

And then the insert function can be rewritten as follows:

 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 } 

Answer 2

Because you mutate the internal nodes and actually create a copy of them. This copy is never inserted into the tree; it is simply discarded after the change. If after inserting into l and r you reinsert these nodes (with self = .Node(currentNodeValue, l, rightNode) and self = .Node(currentNodeValue, leftNode, r) respectively), then the tree as a whole will be updated. This is a bug / link question.