# Swift Algorithm Club: Swift Tree Data Structure

**URL:** <https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194>\
**Category:** 🎓 Courses & Articles\
**Created:** [July 11, 2016, 1:00pm UTC](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194 "2016-07-11T13:00:31Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![kelvin\_lau](https://assets.chunter.kodeco.com/user_avatar/forums.kodeco.com/kelvin_lau/32/109371_2.png) [@kelvin\_lau](https://forums.kodeco.com/u/kelvin_lau)\
**Post date:** [July 11, 2016, 1:00pm UTC](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194/1 "2016-07-11T13:00:31Z")

</div>

Learn how to implement a Swift Tree data structure through this hands-on tutorial!

* * *
 This is a companion discussion topic for the original entry at [https://www.raywenderlich.com/1053-swift-algorithm-club-swift-tree-data-structure](https://www.raywenderlich.com/1053-swift-algorithm-club-swift-tree-data-structure)

---

<div class="post-metadata">

**Author:** ![tobol](https://assets.chunter.kodeco.com/user_avatar/forums.kodeco.com/tobol/32/90505_2.png) [@tobol](https://forums.kodeco.com/u/tobol)\
**Post date:** [July 11, 2016, 1:24pm UTC](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194/2 "2016-07-11T13:24:28Z")

</div>

I didn’t read full article so I might be wrong but I would suggest to make the “parent” property weak.

---

<div class="post-metadata">

**Author:** ![kelvin\_lau](https://assets.chunter.kodeco.com/user_avatar/forums.kodeco.com/kelvin_lau/32/109371_2.png) [@kelvin\_lau](https://forums.kodeco.com/u/kelvin_lau)\
**Post date:** [July 11, 2016, 3:20pm UTC](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194/3 "2016-07-11T15:20:35Z")

</div>

Good eye @tobol! Fixed

---

<div class="post-metadata">

**Author:** ![leokwanbt14](https://assets.chunter.kodeco.com/user_avatar/forums.kodeco.com/leokwanbt14/32/106989_2.png) [@leokwanbt14](https://forums.kodeco.com/u/leokwanbt14)\
**Post date:** [July 11, 2016, 7:22pm UTC](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194/4 "2016-07-11T19:22:58Z")

</div>

Great tuturial @kelvin_lau, any suggestions on prime use cases for beginners to start implement trees in side projects?

---

<div class="post-metadata">

**Author:** ![kelvin\_lau](https://assets.chunter.kodeco.com/user_avatar/forums.kodeco.com/kelvin_lau/32/109371_2.png) [@kelvin\_lau](https://forums.kodeco.com/u/kelvin_lau)\
**Post date:** [July 11, 2016, 10:40pm UTC](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194/5 "2016-07-11T22:40:42Z")

</div>

Thanks @leokwanbt14!

I’d say anything that requires a custom hierarchical structure is fair grounds to use trees. Perhaps in a game you wanted to lay out a skill tree?

---

<div class="post-metadata">

**Author:** ![mayurtolani](https://assets.chunter.kodeco.com/user_avatar/forums.kodeco.com/mayurtolani/32/81494_2.png) [@mayurtolani](https://forums.kodeco.com/u/mayurtolani)\
**Post date:** [July 12, 2016, 8:35pm UTC](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194/6 "2016-07-12T20:35:52Z")

</div>

Why was the parent property made weak?

---

<div class="post-metadata">

**Author:** ![lucianboboc](https://assets.chunter.kodeco.com/user_avatar/forums.kodeco.com/lucianboboc/32/111788_2.png) [@lucianboboc](https://forums.kodeco.com/u/lucianboboc)\
**Post date:** [July 12, 2016, 10:03pm UTC](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194/7 "2016-07-12T22:03:21Z")

</div>

@mayurtolani to fix the retain cycle, parent has a reference to the child, the child must have a weak reference back to the parent.

---

<div class="post-metadata">

**Author:** ![jasdeep](https://assets.chunter.kodeco.com/user_avatar/forums.kodeco.com/jasdeep/32/36827_2.png) [@jasdeep](https://forums.kodeco.com/u/jasdeep)\
**Post date:** [July 12, 2016, 11:28pm UTC](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194/8 "2016-07-12T23:28:20Z")

</div>

Great tutorial, and very easy to grok explanation. Please do more of these! @kelvin_lau

---

<div class="post-metadata">

**Author:** ![msheaver](https://assets.chunter.kodeco.com/user_avatar/forums.kodeco.com/msheaver/32/35604_2.png) [@msheaver](https://forums.kodeco.com/u/msheaver)\
**Post date:** [July 12, 2016, 11:34pm UTC](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194/9 "2016-07-12T23:34:59Z")

</div>

How would I go about deleting a node in this scenario, or moving a node to another parent?

---

<div class="post-metadata">

**Author:** ![createch](https://assets.chunter.kodeco.com/user_avatar/forums.kodeco.com/createch/32/109646_2.png) [@createch](https://forums.kodeco.com/u/createch)\
**Post date:** [July 13, 2016, 12:21am UTC](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194/10 "2016-07-13T00:21:17Z")

</div>

hotBeverage.addChild(chocolate)  
should be hotBeverage.addChild(cocoa)

---

<div class="post-metadata">

**Author:** ![kelvin\_lau](https://assets.chunter.kodeco.com/user_avatar/forums.kodeco.com/kelvin_lau/32/109371_2.png) [@kelvin\_lau](https://forums.kodeco.com/u/kelvin_lau)\
**Post date:** [July 13, 2016, 1:39am UTC](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194/11 "2016-07-13T01:39:18Z")

</div>

Basically what @lucianboboc said.

Another way to put it is, make sure 2 objects don’t keep a “strong” reference to each other.

---

<div class="post-metadata">

**Author:** ![kelvin\_lau](https://assets.chunter.kodeco.com/user_avatar/forums.kodeco.com/kelvin_lau/32/109371_2.png) [@kelvin\_lau](https://forums.kodeco.com/u/kelvin_lau)\
**Post date:** [July 13, 2016, 1:54am UTC](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194/12 "2016-07-13T01:54:06Z")

</div>

@msheaver

Try approaching those problems by utilizing the `search` method. Since we do have a `parent` property for each node, the rough idea for deleting is quite simple:

1. search for the node you want to delete (you can reuse the `search` function you made in this tutorial)
2. travel to the parent via the `parent` property in the node
3. delete the node from the parent’s `children` array

Moving to another parent follows a similar pattern, and you can make use of the `search` and `add` functions as well! If you get stuck, make a post here and I think everyone would be interested in helping 🙂

If you get the solution though, consider making a PR in the Swift Algorithm Club repository 😃

---

<div class="post-metadata">

**Author:** ![kelvin\_lau](https://assets.chunter.kodeco.com/user_avatar/forums.kodeco.com/kelvin_lau/32/109371_2.png) [@kelvin\_lau](https://forums.kodeco.com/u/kelvin_lau)\
**Post date:** [July 13, 2016, 1:58am UTC](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194/13 "2016-07-13T01:58:00Z")

</div>

@cretech

The solution should still compile fine, but I agree it could be clearer to switch the property name from `chocolate` to `cocoa`.

Thanks!

---

<div class="post-metadata">

**Author:** ![msheaver](https://assets.chunter.kodeco.com/user_avatar/forums.kodeco.com/msheaver/32/35604_2.png) [@msheaver](https://forums.kodeco.com/u/msheaver)\
**Post date:** [July 13, 2016, 12:22pm UTC](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194/14 "2016-07-13T12:22:06Z")

</div>

I think I am close with the following implementation:

```
extension Node where T: Equatable {
  func delete(node: Node<T>, value: T) {
    // ensure that node exists
    if let returnedNode = node.search(value) {
      // ensure that returned node has a parent
      if let parent = returnedNode.parent {
        let childIndex = parent.children.indexOf(returnedNode)
        parent.children.removeAtIndex(childIndex)
      }
    }
  }
}

```

…except for the line that finds the index of the node:

```
let childIndex = parent.children.indexOf(returnedNode)

```

How do I correctly get the index of the child?

---

<div class="post-metadata">

**Author:** ![kelvin\_lau](https://assets.chunter.kodeco.com/user_avatar/forums.kodeco.com/kelvin_lau/32/109371_2.png) [@kelvin\_lau](https://forums.kodeco.com/u/kelvin_lau)\
**Post date:** [July 13, 2016, 6:49pm UTC](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194/15 "2016-07-13T18:49:05Z")

</div>

`let childIndex = parent.children.indexOf { $0 === returnedNode }`

---

<div class="post-metadata">

**Author:** ![bush](https://assets.chunter.kodeco.com/user_avatar/forums.kodeco.com/bush/32/62452_2.png) [@bush](https://forums.kodeco.com/u/bush)\
**Post date:** [July 23, 2016, 5:14pm UTC](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194/16 "2016-07-23T17:14:55Z")

</div>

I am running Xcode 8 and I know both Swift 3 and Xcode 8 are in beta. I am just trying to figure out why I am getting this error, and what exactly does it mean. I adjusted the method to follow the new Swift 3 guidelines. I am getting an error on the lines in which I add the child to the parent. I get the error Execution was interrupted, reason: EXEC\_BAD\_ACCESS (code=EXC\_I386\_GPFLT)

I get this error as well when I copied and used the example code directly in xcode as well.

class Node {  
var value: String  
var children = Node  
weak var parent: Node?

```
init(value: String) {
    self.value = value
}

func add(child: Node) {
    children.append(child)
    child.parent = self
}

```

}

let beverages = Node(value: “beverages”)

let hotBeverage = Node(value: “hot beverage”)  
let coldBeverage = Node(value: “cold beverage”)

let tea = Node(value: “tea”)  
let coffee = Node(value: “coffee”)  
let cocoa = Node(value: “cocoa”)

let blackTea = Node(value: “black tea”)  
let greenTea = Node(value: “green tea”)  
let chai = Node(value: “chai”)

let soda = Node(value: “soda”)  
let milk = Node(value: “milk”)

let gingerAle = Node(value: “ginger ale”)  
let bitterLemon = Node(value: “bitter lemon”)

beverages.add(child: hotBeverage)  
beverages.add(child: coldBeverage)

hotBeverage.add(child: tea)  
hotBeverage.add(child: coffee)  
hotBeverage.add(child: cocoa)

coldBeverage.add(child: soda)  
coldBeverage.add(child: milk)

tea.add(child: blackTea)  
tea.add(child: greenTea)  
tea.add(child: chai)

soda.add(child: gingerAle)  
soda.add(child: bitterLemon)

---

<div class="post-metadata">

**Author:** ![mayurtolani](https://assets.chunter.kodeco.com/user_avatar/forums.kodeco.com/mayurtolani/32/81494_2.png) [@mayurtolani](https://forums.kodeco.com/u/mayurtolani)\
**Post date:** [July 24, 2016, 3:56am UTC](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194/17 "2016-07-24T03:56:56Z")

</div>

what does `indexOf($0 == returnedNode)` mean exactly and why doesn’t `indexOf(returnedNode)` work?

---

<div class="post-metadata">

**Author:** ![kelvin\_lau](https://assets.chunter.kodeco.com/user_avatar/forums.kodeco.com/kelvin_lau/32/109371_2.png) [@kelvin\_lau](https://forums.kodeco.com/u/kelvin_lau)\
**Post date:** [July 24, 2016, 6:18am UTC](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194/18 "2016-07-24T06:18:17Z")

</div>

Seems like an interesting issue with the `weak` semantics here. Xcode 7.3 works fine. I’ll investigate further.

---

<div class="post-metadata">

**Author:** ![kelvin\_lau](https://assets.chunter.kodeco.com/user_avatar/forums.kodeco.com/kelvin_lau/32/109371_2.png) [@kelvin\_lau](https://forums.kodeco.com/u/kelvin_lau)\
**Post date:** [July 24, 2016, 10:28am UTC](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194/19 "2016-07-24T10:28:04Z")

</div>

TL;DR - Our custom `Node` object doesn’t conform to `Equatable`, so we don’t get to use the convenient version.

Long version:

Let’s start off with a working example:

```swift
let stringArray = ["Hello", "Cats", "Dogs"]
print(stringArray.indexOf("Hello")) // prints 0

```

The above compiles fine. However, we can’t do the same with our `Node` object:

```swift
let helloNode = Node<String>(value: "Hello")
let catNode = Node<String>(value: "Cat")

let nodeArray = [helloNode, catNode]
print(nodeArray.indexOf(helloNode)) // compiler error

```

To understand why, you’ll need to dig a bit deeper into where the `indexOf` method comes from.

## CollectionType Protocol

The `CollectionType` protocol is adopted by types that can be treated as a _collection_, such as Swift arrays. This protocol has a suite of methods, and amongst them is the `indexOf` method.

Inside the `CollectionType` protocol, `indexOf` has the following signature:

```swift
@warn_unused_result func indexOf(@noescape _ predicate: (Self.Generator.Element) 
  throws -> Bool) rethrows -> Self.Index?

```

Let’s simplify that a bit so we can digest it a little easier:

```swift
func indexOf(predicate: (Self.Generator.Element) -> Bool)

```

The generalized version of `indexOf` takes in a closure of the form `(Self.Generator.Element) -> Bool`. The idea is you’ll provide the logic for it to match what you want to find. For example:

```swift
let nodeYouWantToFind = Node<String>(value: "Hello")
nodeArray.indexOf { $0 === nodeYouWantToFind }

```

However, by using _protocol extensions_, the Swift Standard Library extends the `CollectionType` protocol by providing a overload of `indexOf`. You may think of this one as the “convenience” method.

This one abstracts away the closure and just asks for the element, allowing you to call the method without supplying a closure. Continuing from the above example:

```swift
nodeArray.indexOf(nodeYouWantToFind)

```

Using this convenient method has some requirements though. Your type must be equatable to expose it. In this case, the `Node` class did not conform to equatable, so you aren’t able to use the convenient version of `indexOf`.

---

<div class="post-metadata">

**Author:** ![wm\_j\_ray](https://assets.chunter.kodeco.com/user_avatar/forums.kodeco.com/wm_j_ray/32/40137_2.png) [@wm\_j\_ray](https://forums.kodeco.com/u/wm_j_ray)\
**Post date:** [August 30, 2016, 2:41am UTC](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194/20 "2016-08-30T02:41:07Z")

</div>

Kevin,

Under xCode 8b6 I was doing fine until I added the generic portion of your tutorial. For some reason I’m getting an:

```
 error: Execution was interrupted, reason: EXEC_BAD_ACCESS(code=EXC_i386_GPFLT) on the .addChild(node:XXXX).

```

I’m not sure what the issue is and any pointers would be greatly appreciated.

thanx in advance

[Next page](https://forums.kodeco.com/t/swift-algorithm-club-swift-tree-data-structure/17194.md?page=2)