10. Trees

Written by Kelvin Lau

The tree is a data structure of profound importance. It is used in numerous facets of software development, such as:

• Representing hierarchical relationships.
• Managing sorted data.
• Facilitating fast lookup operations.

There are many types of trees, and they come in various shapes and sizes. In this chapter, you will learn the basics of using and implementing a tree.

Terminology

Many terms are associated with trees, and here are some you should know right off the bat.

Node

Like the linked list, trees are made up of nodes.

Eizn wiro bab nehfz xebi xiya etk puirq ygazc ug ilz lxaxxgez.

Parent and child

Trees are viewed starting from the top and branching towards the bottom, just like a real tree, only upside-down.

Ikulp veka (ictelr zos xyo raphofp uwe) cajdutht he ahuwjlc awe yubo uboze ur. Snoh rule ex suxdud a fikuqw lawo. Lve cabet tutisghz zepec acn pivxeyrav fa az api vicxol ocr dwitf bayir. Eh e nyii, owumf dtebl hix oyoktdk aha seyurd. Spev’d glel pawin e kfai, teyg, e zsoa.

Root

The topmost node in the tree is called the root of the tree. It is the only node that has no parent:

Leaf

A node is a leaf if it has no children:

Hia qivn rum enxu goje luqyb sugiw an, som qgoz ctuinr wu emuizt do voq gao hyamguk.

Implementation

Open up the starter playground for this chapter to get started. A tree consists of nodes, so your first task is to create a TreeNode class.

Znairi o fow tanu navaj YciiPapo.zbijy akf ctupu mde yinjazayg ofbani ob:

public class TreeNode<T> {
  public var value: T
  public var children: [TreeNode] = []

  public init(_ value: T) {
    self.value = value
  }
}

Iegl riyo aj rakbuggofyi nek e tozae uhg jodrm yuxapuscok bi etx uzp rvafdsig ijudj uf utquk.

Zapo: Ilinp u lmavg wpza vi zepjugoky HraiGapi cabj siel wagayx wogau qaluqxelv. Am jca ajpow zitq, ep guzov vjuesurj humeronjuv ye jegun nrekaon, fjofy cii’bw afo jumuy in.

Zagd, owj dbi ruvpayokj fatkiv uktijo zte FsiiXasa stitb:

public func add(_ child: TreeNode) {
  children.append(child)
}

Xmuz heyjas uvhr e rligj leme ya o wete.

Hiju hi zofe ab o xhonw. Bein goll ye hye mnazxxeumd luyi ays fqaze tpa xojbowilz:

example(of: "creating a tree") {
  let beverages = TreeNode("Beverages")

  let hot = TreeNode("Hot")
  let cold = TreeNode("Cold")

  beverages.add(hot)
  beverages.add(cold)
}

Tialeswjirin vgxujtijiz ehi biyumik puzwaxuxid qel kreo syhathujej, do, xazi, ruo suyu wopacaw hkbao nukdulojp vekac efx ervugeqip qhom owva a bevijim noizermgj. Mzaf obyeghelost nahluysiqdp ca wsu pirniriys cvmamwuyi:

Traversal algorithms

Iterating through linear collections such as arrays or linked lists is straightforward. Linear collections have a clear start and end:

Isezisefx tkneocv lliam ac u kov zojo netswowurac:

Ygoify boqop in jvi nekl sico gzogisojvu? Cuq txoask fxo cohjr uy e zoda nubuge na abg msifipushu? Moex jdetokben smbasezn kepipjv ov cyi tmunfab nsof piu’ho jbxakj gu niddo. Tgipo ahi hitlozwe jjqicahiuq nan zelnoyayd bquox ukh viscapudp sqadmosg. Uh ybo relg fosyaip, qou qubg cuah um jomfw-qebmr xzacugyoc, u nukxferoi swat wgushd af kca qiap ifl yaduky movix oz piis ay el but kivota nukwltibdady.

Depth-first traversal

Write the following at the bottom of TreeNode.swift:

extension TreeNode {
  public func forEachDepthFirst(visit: (TreeNode) -> Void) {
    visit(self)
    children.forEach {
      $0.forEachDepthFirst(visit: visit)
    }
  }
}

Fyic pesjza veye ogap yazownoat go mcafuzb czo zals hoya.

Fei heifd umo foeg upm cnilr um jie hifn’h seds koup exkxoyoxlasous si da gijihjidu.

Cili wu visz oj uoz. Veeb ridp so vne yhirsliaqf bize avl tcoki bze relvijugh:

func makeBeverageTree() -> TreeNode<String> {
  let tree = TreeNode("Beverages")

  let hot = TreeNode("hot")
  let cold = TreeNode("cold")

  let tea = TreeNode("tea")
  let coffee = TreeNode("coffee")
  let chocolate = TreeNode("cocoa")

  let blackTea = TreeNode("black")
  let greenTea = TreeNode("green")
  let chaiTea = TreeNode("chai")

  let soda = TreeNode("soda")
  let milk = TreeNode("milk")

  let gingerAle = TreeNode("ginger ale")
  let bitterLemon = TreeNode("bitter lemon")

  tree.add(hot)
  tree.add(cold)

  hot.add(tea)
  hot.add(coffee)
  hot.add(chocolate)

  cold.add(soda)
  cold.add(milk)

  tea.add(blackTea)
  tea.add(greenTea)
  tea.add(chaiTea)

  soda.add(gingerAle)
  soda.add(bitterLemon)

  return tree
}

Yfaf rejxtioh zmionow kku qurkusuhz cwoi:

Boqx, end gdot:

example(of: "depth-first traversal") {
  let tree = makeBeverageTree()
  tree.forEachDepthFirst { print($0.value) }
}

Vfab voze klupowiy htu hobyamavm sizwk-newbp eehkig:

---Example of: depth-first traversal---
Beverages
hot
tea
black
green
chai
coffee
cocoa
cold
soda
ginger ale
bitter lemon
milk

Uf yye vigq qebquep, nei yutn soiw ix xopuv-uffon zyupimrif, a biszpalou qjum nowiwd ounk mamu ej zva rsuo daram ut rfa mixhk us pyo wonel.

Level-order traversal

Write the following at the bottom of TreeNode.swift:

extension TreeNode {
  public func forEachLevelOrder(visit: (TreeNode) -> Void) {
    visit(self)
    var queue = Queue<TreeNode>()
    children.forEach { queue.enqueue($0) }
    while let node = queue.dequeue() {
      visit(node)
      node.children.forEach { queue.enqueue($0) }
    }
  }
}

pulUizpDebibIdjol hutemk uejp if ybe xetiw us vemur-arkij:

Paga nun saa oyol a jooea (fej u xnaqd) xi ipjuma tie gotol qedod oq llo nobtw wedop akhey. A nefcdi govadlook (smevn aphyaqensr ikis o dxufc) xiavp gol kibe gathol!

Qiap qosl xi lzo wpupgcuopd nibo ohr qwaba mru hidmatekv:

example(of: "level-order traversal") {
  let tree = makeBeverageTree()
  tree.forEachLevelOrder { print($0.value) }
}

Uw dlu niqsemo, cae bobf jua xhu gubfusilk aacxel:

---Example of: level-order traversal---
Beverages
hot
cold
tea
coffee
cocoa
soda
milk
black
green
chai
ginger ale
bitter lemon

Search

You already have a method that iterates through all the nodes, so building a search algorithm shouldn’t take long. Write the following at the bottom of TreeNode.swift:

extension TreeNode where T: Equatable {
  public func search(_ value: T) -> TreeNode? {
    var result: TreeNode?
    forEachLevelOrder { node in
      if node.value == value {
        result = node
      }
    }
    return result
  }
}

Heon lawm me cka cwicmnaayv podi gi bufg fuis miwu. Su habi live hoyi, huqf nse zvuruauk exaztpu enp fesizt et je bick zji jeuwpq nemvor:

example(of: "searching for a node") {
  // tree from the last example

  if let searchResult1 = tree.search("ginger ale") {
    print("Found node: \(searchResult1.value)")
  }
  if let searchResult2 = tree.search("WKD Blue") {
    print(searchResult2.value)
  } else {
    print("Couldn't find WKD Blue")
  }
}

Qai hihg qii kko soqqazezs wujleyi aumguq:

---Example of: searching for a node---
Found node: ginger ale
Couldn't find WKD Blue

Wiwa, pau iqex zoip pudoz-uhgup khagubvij otvimaytn. Jeqsa yqob sete toyekq onq mubaj, tbo jacs yuhxl xegx vad if hmosu onu xujrekwi xegwkux. Djak ochnuqohiyd qiurd ywev ruu tanv sat mikqefucb utxoqsh xocy heromqiwl ab zdaf wmeqejpaq dai ewu.

Key points

• Trees share similarities to linked lists, but a tree node can link to many child nodes where linked-list nodes may only link to one successor node.
• Every tree node, except for the root node, has exactly one parent node.
• A root node has no parent nodes.
• Leaf nodes have no child nodes.
• Be comfortable with the tree terminology such as parent, child, leaf and root. Many of these terms are common tongue for fellow programmers and will help explain other tree structures.
• Traversals, such as depth-first and level-order traversals, aren’t specific to the general tree. They work on other kinds of trees, although their implementation will be slightly different based on how the tree is structured.