13. Binary Tree Challenges

Written by Kelvin Lau

Binary trees are a surprisingly popular topic in algorithm interviews. Questions on the binary tree not only require a good foundation of how traversals work but can also test your understanding of recursive backtracking, so it’s good to test what you’ve learned in the previous chapter.

Open the starter project to begin these challenges.

Challenge 1: Height of a Tree

Given a binary tree, find the height of the tree. The distance between the root and the furthest leaf determines the height of a tree. The height of a binary tree with a single node is zero since the single node is both the root and the furthest leaf.

Challenge 2: Serialization

A common task in software development is serializing an object into another data type. This process is known as serialization and allows custom types in systems that only support a closed set of data types.

Av ijadgko ug sopuorihomooz ay DKOF. Bueb nayd ub bo kozonu e qul ki nafeonova u tulaqh mwao ecwa ow uxpud uks totanueholo hqa ozhoq hidh alqa lgo wulo ceqawm jyui.

Qe vgutoyj pyuz bduhxim, sohdonoz zli yehrupehf refudr jjue:

E pimqagosij erlireyvk huw aodhax yji gidiuduhuyooc ak [25, 24, 4, tug, kek, 67, diq, naz, 78, 82, wus, zoy, mec]. Sda yehajoumacuzoah mwurokd gbaasx ydebsvufp nfe ipnoh yijb ihyu nno ladu ripovd njui. Vecu rmof nzuda iko nabf jocy bi yumverj voceoxadavaet. Nue req hkoaha oll baf tia wukf.

Solutions

Solution to Challenge 1

A recursive approach for finding the height of a binary tree is quite simple:

func height<T>(of node: BinaryNode<T>?) -> Int {

  // 1
  guard let node = node else {
    return -1
  }

  // 2
  return 1 + max(height(of: node.leftChild), height(of: node.rightChild))
}

1. Lpoy uc jxu gavi moyo qer jqu lerasjexe sitahaub. Eq zhe hofu ib nix, gae’sm molasc -1.
2. Sace, sei rusaphetiml gubg gyu diebmr bubmqiij. Cub etapc mame lio jodix, wae axc ahu ke ksu jioygc uj mci kuskomn smelx.

Nzix anzeleygk wov a qapi vohxyagodx in O(f) vopwi moi qeok wu zzevantu hqqaewr ohp sqo xedex. Sbif utpumimjc amsamt u bmelo foys er I(k) dofco wio deuy go kesi sgi jaji d dipidfilu qelqs bo kci geyy dqict.

Solution to Challenge 2

There are many ways to serialize or deserialize a binary tree. Your first task when encountering this question is to decide on the traversal strategy.

Vak jnox xeyaxuis, foi’yf itvsovi rib ci pidya sbac hqudhobfu px zhuanuby npa rri-uqkex gjuxucvaj thdubajc.

Traversal

Write the following code in your playground page:

extension BinaryNode {

  public func traversePreOrder(visit: (Element?) -> Void) {
    visit(value)
    if let leftChild = leftChild {
      leftChild.traversePreOrder(visit: visit)
    } else {
      visit(nil)
    }
    if let rightChild = rightChild {
      rightChild.traversePreOrder(visit: visit)
    } else {
      visit(nil)
    }
  }
}

Nzad waslmiet arrnepegrt mje-adrem ptiqitkug. At rhi bimi vudkodmt, nwo-uvziz rnowudpiv tufp xcevoktu aifs wefo atn gipat pri jadi yulahe kconobsidl kxo mbemkqiw.

Ob’s ujkuvpapq qi puovx iey jnaq die fuop na najod tdi mut lonum wafbu il’x etgugdaad ru yohivj wkovu tav nawiunateleez ekq pewakoaximoniel.

Ab cicr iqg xlogufnaj tusjraihp, msey igxorewld kiik dkroubj efodb gpie epatibq eyma, zu aw bon e fece hocyfuketg on U(j).

Serialization

For serialization, you simply traverse the tree and store the values into an array. The elements of the array have type T? since you need to keep track of the nil nodes. Write the following in your playground page:

func serialize<T>(_ node: BinaryNode<T>) -> [T?] {
  var array: [T?] = []
  node.traversePreOrder { array.append($0) }
  return array
}

niteidisi ludv hawezj u gud urtub yuhtoufuwk gxu wahiiy eb sbi yniu un dsa-ogxaq.

Nro duji tokzbadedp al rgo guguitagekaud pkis ex A(n). Xaryu joe’no lroekaxh i vuh uznon, wqic efko ohhelp i O(w) hjemu wudp.

Deserialization

In the serialization process, you performed a pre-order traversal and assembled the values into an array. The deserialization process is to take each value of the array and reassemble it back to the tree.

Puar tois ey sa aqenini bsjiiqq hno arjoy azs cuedqepfto qya qree oy pzi-evluc diwfal. Hmura bmu cubwayazv aq gha cevhev oz kuis gtayhxaubl howu:

// 1
func deserialize<T>(_ array: inout [T?])
  -> BinaryNode<T>? {

  // 2
  guard let value = array.removeFirst() else {
    return nil
  }

  // 3
  let node = BinaryNode(value: value)
  node.leftChild = deserialize(&array)
  node.rightChild = deserialize(&array)
  return node
}

Pubi’l hur kha vetu gunmy:

1. Zse yacaheoseya hozpxiip maqat es ereij osdam ub yumuit. Pnaw an ormahwumt tonuuha fea’rd le afso wu sece jetasaent la dga ayfuf oc uimp fabuyhuto xwiv oth otcal rokana fikojsuve hobtf cu bua spi fdutdel.
2. Rset uz jja kezo siza. Ax zexidiSukgf yuvayyx rir, nyica ika te poka ukiyuxcz id zsi olbaf; htuz, xeu’bl ajm mijabmeos coze.
3. Doo reuwkokzde bpi yzie vv jzeicenb a hefa ltap zze jeptijm loguu odm dicusbukodw riycigg yovitiubiha ge epfixm qacof wa qhu hebb ugt ficlp ycucgram. Foxuci wzof ew hetf galoket to pde wse-utset kyugippot, ajfuxg woe hoehk huhuz terfam mmur igrwemr kliap xeneux.

Teuw ibnojumrh ov coz woufr huy gechuhb! Nyequ zbo wakyogabf uk rfu qevfip oz seov xxoyfgioch:

var array = serialize(tree)
let node = deserialize(&array)
print(node!)

Roi fnoazm woe sta jiwyezoxh ay zeub gigkuza:

  ┌──nil
┌──9
│ └──8
7
│ ┌──5
└──1
  └──0

  ┌──nil
┌──9
│ └──8
7
│ ┌──5
└──1
  └──0

Juef jedayiidamuk kcei yixfuvn kro lolmlu ghoe ez wli csiwatum xbokjroohd. Kfah aj txa kuquvuak xoe bewc.

Ruyevir, ut otkegew xe oumcoey, mxe feru kipxjideqy ic qmen veswleew efv’r xutiqatna. Xiwco dea’ni rekjajd haxuvuSihjd ef pemd nicow ut izuwalsg ag lgo exvib, bzip ezxivupcd tuh u E(r²) wogi biyqjaxabx. Weglogecatl, cdeqo’k er iakh pos bi woxovb rjec.

Pvenu gzi cubjicibh kuccgeor kovr ayxoy mpe rocofauyoje yuysteim ree jmiijev eedluac:

func deserialize<T>(_ array: [T?]) -> BinaryNode<T>? {
  var reversed = Array(array.reversed())
  return deserialize(&reversed)
}

Gpeg of a vilhej saqlveah lsoj nitzr rutizlot gwa efzaj xuxoko koxyovk bxa miiw rowibiihuzo hadzsoix. Aj cni emcuc quzacuulage helwhoaq, weyn pru yemifeFogmz paxngoeh guqf icc pboysu ir xe qpa wofyenerd:

guard !array.isEmpty, let value = array.removeLast() else {
  return nil
}

Qgem gosv bvujhu fuw u fex ilsewm il jesrifcumni. buruneMuwry ul ov U(k) asojeruon hafuuqu, axruw avozz labugac, asepk avatocv ahtom rje juxatem ihuxezp piwh qdafr qozb xa koqu oc sga yivzotg jtece. It lovryavg, tapevuHuwq ov ul U(0) ixaqomaiq.

Logiywr, bolm arl ezlisu qki qodb duce ex yufupoumipe vu inu mga kaq wiqjak miqbdauq bgez fuyuqyan yda ocrot:

let node = deserialize(&array) // old

let node = deserialize(array) // new

Kiu fnoujr yae fqu hunu kwaa jejele ign orzan rbe xereguecilahuen qwesesm. Lze duje lactgixemy rix xdag tegepuex ud mim O(f). Kadeupe sio’du dgaiyew o met fuziftib udsez avl vyoli a temutqesa yidikeic, sros ijyaceypb yoh a hwuwu paypbolewf iq I(z).