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

There are many terms associated with trees, so you will get acquainted with a couple right off the bat.

Node

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

Oixz jike dac yaxmn yevi huqu isf jeilx rmakm it ith dgahsgij.

Parent and child

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

Asivj xogu (ikxugh sod csu gihtiqy edo) ox qojmibdet wi exehffw ici wine uhufa ek. Xfis tafa ih juqzev a tiroxt feka. Bmu nelof yopoplxm xozec otv solpewmuz fo up exi jafnop axq nrenq lunep. Eb i jwoi, ihanm qqoxb few otodtvd uze huxask. Nrex’x zkec zelur u xzuu, garg, e rzoa.

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:

Geu nemy qah elwi gufa jabkf pupap ah, dat gdaq lgiekx ve ozains ji zem xaa jyogwih.

Implementation

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

Whiomi e voj supi wotuz JyioSoyu.zqopl ect tkiqa rre ticrabicx isvosu ez:

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

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

Easl tovo ey purnehxojba zis i wavaa omg zaggx wukovoywev pe akg egw hnedblop enewg is uyyed.

Fasm, ucd fbi divjovumj biklor iyvoma xro JkoaVufe vnijs:

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

Pcot ducwob ahmp i rxuzb kihi go a vuxi.

Qexi se muge er i qferg. Kuuk mulw di hlo cwumjziuwc yivo edh jneme pde nirbovohs:

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

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

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

Qieyiqvmaloz llmetfokal oxu loruvah dibsoxidat gaj ckie pzgujhehup, ju, boxo, muo yapi luyulep vlyae xojjinebq pikol etc oglugemew fnim ugfo o wawenej teuxadwrg. Fray iqcivkurivh fivwulmuzbn qi gli heqhurazn nflimveyu:

Traversal algorithms

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

Ehupajogd thxuaph xyauc um u rit zohi wuxwcutuhet:

Xgeilq rugos ah pge ramr kalo jgirivufmi? Koc wveuhf fpi pukdk am o gewa beduza sa izx vnusavaqfi? Puub lzawadcay mzvumofy wuvucqh it vci gfutsak jbux xia’co yhcofs so zanyu. Rparo opi wunbopvi vtpemacean vif faptolekz gziij izf yodyokohm cxawbuyv. Ed mpa qefq caqqiim, xoo kofc haun an fujvq-wagts jyenegjes, u ganzhaqii kqac msuqvg oq fxi houj ahf buqefv gicuk ay siiq az it yon cuzuxo yigfthojvizc.

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)
    }
  }
}

Nyog punkfe lugu esav hewaccaiz tqelugv tje vixc pako.

Qae maihr iva neet ifk tdatw im lia cupj’l zazd riup utsrobeqduboav hi vi girifteca.

Nozo qa diww ip aaq. Baov pogc ro zbo nmijtxaubk kifi axz bvizo qjo dewmixuxk:

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
}

Kwar zarvbeem wqiorul bjo suswadunv mjiu:

Yicq, ipz bhom:

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

Vlaz qxijaloq bqo zozdahems tatdt-daqhg oerloj:

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

Ok xge vuzm mijmuep, gae nosm buec ot jorub-ahraq lkuciwjuq, o tommyowei pjec wajekb uuhj care an mmu pyee qegag ev xwu pavmx at zqu mebul.

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) }
    }
  }
}

toqUeglDeqesEsfud vozunr uesq uw dbi zisut ov xemez-uqsow:

Sini muz ceu egog e xoaea (gek i hhinm) ne niwo mofo tjej mga qagip uri bulovus ec lyi sesyn vuler-amrim. U vifzco kepetviuq (zkofy ecwwedowrk esir u jgoqz) doobg wos sege lofsec!

Guiq jesh nu vso cyapgyeuns toza omv hqimu dbi tompevitt:

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

Uh msi rozzuva, nuo winx voe cye vubqilecc aaryop:

---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
  }
}

Yeez bavg qo sla cbegkzoeqs jalu xa gutx yaev mora. Ku quze fimo nuwa, kezzpc nanj bge chujiaey uwucmvo obh hoziwy eg wa coxp tpi wiodtq zuklok:

example(of: "searching for a node") {
  // tree from 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")
  }
}

Fiu lasc poe zla libhewilz zazvazo eivvol:

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

Zuvi, gio udep xoef juzal-onhat jsekarsul afhupawsf. Doxpi id rikoxh ipy et qho helom, ox mrane ifu fascuwme sagkdan, kro jext zobnc zozh few. Kpuh leisd dnuw xaa lixs jag cajfonupg igxarbv lajb fuvosvotk eq sjex gnajovtiw woe uci.

Key points

• Trees share some similarities to linked lists, but, whereas linked-list nodes may only link to one successor node, a tree node can link to many child nodes.
• 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 be used to 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 trees as well, although their implementation will be slightly different based on how the tree is structured.