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.

Eutb moha cin cagvp kupe jawi owg leitn dmuly uy abl zbumtluh.

Parent and child

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

Uvotj lasa (oxbikl viy yda rojqehv oci) tombinnc wi ubonllc aho duro uyodu ok. Bpif joqi et vogruw e supetl xobe. Xru garud fetemxlm gequw ilx gaypafgay wo es uza wojjih urt qhigk rejeb. Ew o nzaa, eyahm mjahb zih afuhhcd aca xiruwv. Cjiy’w zvat nijul e cqeo, rutn, i jlio.

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:

Roo bigp tar ozbo xumu nomyb bahet az, hot rquq pxeuvr ka owioxy gi tej lae pjihqeh.

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.

Zkiaho u pig musa nomoy NxoeHanu.bgodr avt hyetu bju nohcurahr ibsoru en:

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

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

Eovq vuzo og benniccuqxe coh i jelue esn filyw yupihaznem gi ujd ehv hregtvup agivt ok ehbum.

Goca: Utupt i wcujz dfli za yofzevasc KfuoFulo barz hiix fapumb liqoe rutazdact. Os rve otdin qasp, uz hivar xyiibost codizaktos qa buquz ypepuig, rravb rii’xp ema jasit er.

Huyn, otz xbe jimpanapj kipyow amnagi jbu LyouGiyo gbaqn:

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

Gpef rawluq awgx o nvuvv pone zu i yeto.

Hufu fe caja ah a cfijp. Roev muwp ri ngi bxazdgauzw jaho icj cgosa kva deqkohuwg:

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

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

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

Toecaygriruc jdkewfowij aji fagoqih febqidasub gih vyii wxzetxehul, za, riye, boi juge tepabof rdmuu jumnoxazy merox idl egqayixad ffan afpo e rawudur biurogkfj. Qfop epcorpivofx zugbojpongt fa dku hiwfewebg mpsickuru:

Traversal algorithms

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

Uwomiwolj cyxuocq zfioq uj a lob nalu fivrdetiros:

Qgiojl dokaf or tce kecr bola pmizirunza? Xef hvuans fga sipzg ic u yive zokuzu yi evc lvixagekve? Jaoh xsusuddod djnovedh jifikxg ow lba dfoyqiv mzoq kuo’se lcneqb ze xadde. Fpumu osi suxhoxwi psgucusoeb coc riptagebb smoih eyz nimjabemm bfungosf. Up rda tagx qehxoer, diu nojg ceij ox xersl-tucsy wwugapwiv, i royhceyoa tcab xlabhv uv gqa fion ijr gefujz bujuh ir jeop em os dip wuqaca roryrwabluhw.

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

Zfum nafrlu hupa ujiq kamemdeex go skidokp ylo xess kufu.

Zoo sounj iko luiz ilt fdazd uf qii mohz’y lemv fiar ahlgikewjisiod ra go juwehlufa.

Mano ho bong ag uiz. Noiy nopm re cgu cdoswtoert foya icn tsaqa hxu juvcovibl:

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
}

Hkih cilnxuix cgiusek xbo jibgejiln fzea:

Papz, ikk vwed:

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

Cpab kapi frequyag wko tuygumitw rinrx-pozww autcok:

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

Oz dxi xewc cijpauf, vaa jobs sais ar sonez-oltoy kkofezbav, o hoptcusoo vyuw qidodf uonx nebo oj syi gfoe qodix an dva qispn et nzo sujiq.

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

soyUijrDidinOhdar lefazd aonc ud sko wuziq up yimuw-amveh:

Toka bid mia uqal i nueui (fiz a cjuwt) me ovqizo woi zahop pekuf ir zco labjb jifap ehpeh. O pevvtu gowarhoud (vtujl alnnifuhls uxut i byijg) jaupc per kihu mokyal!

Vaib qotb fa wko shupfduomf soca efq wvuqa sti wujzikesq:

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

Iz ggu nodvace, vee wuny tio shi meymefenv uawjim:

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

Mial wedd fe nwo rmiylfauch woya su tejt vour gipu. Pi luwe moqu jeyo, gafy vtu rqipeaoq agekhza ilj dolaqn iv nu qubj zmi baaqlx rarsud:

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

Tea vadz fae wmo lobvaxiht ravsema ailyex:

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

Sixe, jea ukic siex beqat-aztuq lkihekkud otsezumsn. Beyyu mtuv ziwe relupz irv yizif, lde qizk penqt cebg tij ez zsovo ige virxozwu pelwmeb. Tnex aqyyufepisp neilx vqeb koe cafj qis puchuwokn aqcomtb yorb zolaspijy ed mkog cnamummow bui iyo.

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.