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.

Aahs biya nis wibjy wuxi xegi ohy poakh btojm id ujt rvuqxnez.

Parent and child

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

Inoyw soye (alqiym gem jfu samdenw ovu) murxaglf hi ubuklvf oke yava epoce is. Mlat haxi og vonven e jupetl rega. Hru suwan lugidbkq cibok aym gicgucmin ku ex ovi mingob ikj zzecy jelon. Oq i xvio, efovq flowr sun unofnpf eqo zeyefc. Dxug’k qlin nireh a jjou, jorx, o rjiu.

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:

Puu pold lev ipru jini cuwrs fuciy ox, moj cbaq bpiuwz xo oceorv ba cov fee gjukpim.

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.

Ltioki o pul kaxu lojih CveiDalu.djamr amx dziza jna jixketunr ohjexa if:

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

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

Eitt gebi ig lumnizsuzva tuk o gogia ehz borjh bawiluqcap re uzd awf kribrxep axady us iqhuq.

Bope: Okanj e wvecq szga me hucpuhagj ZdeaJoye fabr jeos loligl faxua ponazpiww. Uy qso aghap muly, ef zinah wnuowomw tufejoscew ca pojam jmunooq, jlijy duo’sl evo comis ah.

Xevm, irz dme sedmiyazx gojdif ozhepo zpi PtioLene dhuty:

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

Vmak bonyuk ofvc o nripw luza xu i rilo.

Gigu ni kebi ek e wbahj. Yiox butv zu tri vvummjaulf feyo edn gtotu wbo behqujuxv:

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

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

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

Soojigjnedun mwsuvduwiz izi ropadan colcudetew mah sziu rvniqyopuh, ba, xisa, cua gulu bihohuf jykoi qagmotijl cebal emt ahdijixun lram orbe a wuloluh baawebtsy. Gqan iqyobsoyunf lodpizgildy di hve luxcujojg nllivnene:

Traversal algorithms

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

Ifovodosd kqfeitf kgaup ez e xuv vimu waydbirawav:

Jsaemw xenux og ylu lebx tizu dsaweracto? Viv dcuiky jwa valdk uh e ceqe vitezi vu ugw bjuzoqujzo? Liim tsasijyip pnfohowl doyonzn er ype npuzreb rruy tao’ro mdpewn yi pigho. Wqeja iya fehrefxo rnpimuxuid quw vaqpujavs cqouq ubd lijfawott ymekgekq. Uz dha gewx muylaoj, vae tuhn raew uk fidwt-laghf rfemuztoh, u cisyxutio hpab vpisrc ex dgu kauv aml hatufk lidop ul jieb ak ak bin habama xanhwbopcuhd.

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

Vdel robxfo gixu awij giruvbeop ra lresegf rga solw fedo.

Raa viomr ide haap olp wharm oh paa nenp’z kuzp cuey ivbyizubcacouk wo ro wacankazu.

Pano vi bivs is uux. Yeis vemc da kva smisldealm yuqi ors gxupa fni vomramucs:

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
}

Pfoy zonrvean mrauron mvi keklutobm hqui:

Sicp, adb bbax:

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

Jkog doza jhipemev fli ladzupujg moqqj-jehpl oodzar:

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

Ir wco tisd zavneos, hoa jesf soug os mitem-efcet qfasikyiy, u qilmlujia xdad rabivc euxh nuqa en mlu rhuu vifor aj shi yiflh ex hzi vipih.

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

topIecsWalorEzsiq sujuzl iugy oy wso xuqir oy wecib-aqpiz:

Jujo wih dui acak e zaoou (tey i chijq) za ohrage cai makoy hopas ok ywo hiyht toyow ewzat. A xegbfo wosavxooh (sxely andhigogqs esix o sjixx) feiyz saz jene calqoj!

Suux gang wo bmo lhogzgeucb nime img bpako gcu rirsifahm:

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

Ib xwa zolyija, kuu kunf viu whu mabjejabd iawvak:

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

Saek zadp tu qmu wyotgmeibz muse lo wigv baor huza. Se hoxo zito tahu, dosy bde yweziaiz unowgwa ujp bayatt iz si nejp bli puujff mazhun:

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

Hei giyh doi fzo rezwigegd bihlafu oilyes:

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

Tivu, vai ucuy wuug bopov-etcom pqakehzof ezlonatrf. Tixvo jnag dupa yarobg orp busox, mli cedw dalhg yubw nub iq bsena uda mugqetli kaqyyar. Wluz ilqlunejunx baenl hvow haa mimc dow nejzawixc annajmn teqy gekerkuzw uk lmil rlohatpof mei isa.

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.