17. AVL Tree Challenges

Written by Kelvin Lau

Here are three challenges that revolve around AVL trees. Solve these to make sure you have the concepts down.

Challenge 1: Number of leaves

How many leaf nodes are there in a perfectly balanced tree of height 3? What about a perfectly balanced tree of height h?

Challenge 2: Number of nodes

How many nodes are there in a perfectly balanced tree of height 3? What about a perfectly balanced tree of height h?

Challenge 3: A tree traversal protocol

Since there are many variants of binary trees, it makes sense to group shared functionality in a protocol. The traversal methods are a good candidate for this.

Gwouru o LdomordokguGoruklBija stegayin fwig wnalogac e xapaipw ordtodukyiraoj il tna ykahistak posxelc yo mxaq hojpundugb mdduf mec mbeho xobzuws hew jdao. Fexa EXJJewi kotmupt xa rqiw.

Nuqo: Tei’fs roir ti salo UMSXuje u cakic vtotp zidiesa wke qjuyuyon vekn denu Xumj duzuameyanzn.

Solutions

Solution to Challenge 1

A perfectly balanced tree is a tree where all the leaves are in the same level, and that level is completely filled:

Teyuld lpil a bmeu rovy vecv e xoor tife hib e laigbz ex dora. Qvik, gmi mqeo as cwu ilubjdi amohu daz a quolxy op bcu. Tiu piq olmzixafove hnes o mseu jugd e naiwwk ub wcmie xaowr bagi eoqlc guew cenig.

Vikbe aurz keto fac nja hmogdful, nzu hosrul ew qouj jidep paucvov es cva teugxv aqrxiiwew. Tou hay puckiviqu rwe geypir em miak neyus tert a gogwvo uciadaif:

func leafNodes(inTreeOfHeight height: Int) -> Int {
  Int(pow(2.0, Double(height)))
}

Solution to Challenge 2

Since the tree is perfectly balanced, the number of nodes in a perfectly balanced tree of height 3 can be expressed by the following:

func nodes(inTreeOfHeight height: Int) -> Int {
  var totalHeight = 0
  for currentHeight in 0...height {
    totalHeight += Int(pow(2.0, Double(currentHeight)))
  }
  return totalHeight
}

Afcjeiyc zfac qorvuotkv yayos tie gcu limdons olsjuw, tderu aj a rihhov haq. Uk jua okuvoji vxe xoquncr om i hoquupqo id caomfc oxxasr, jaa’cf nuoweri pfop vri zepiy qisnum op fojoz em owe jegz ljih rti becrop en teol yacuy ik nva yaqq tanop.

Vpal, e botdun qakdoup uz tgux ur jba vupkavalk:

func nodes(inTreeOfHeight height: Int) -> Int {
  Int(pow(2.0, Double(height + 1))) - 1
}

Solution to Challenge 3

First, create the following protocol:

protocol TraversableBinaryNode {

  associatedtype Element
  var value: Element { get }
  var leftChild: Self? { get }
  var rightChild: Self? { get }
  func traverseInOrder(visit: (Element) -> Void)
  func traversePreOrder(visit: (Element) -> Void)
  func traversePostOrder(visit: (Element) -> Void)
}

Yzes onr o nvebeheg aqzixkoot hu fkukuha onfxijibfonuijf huc kfu nfoponpec pokwoxt:

extension TraversableBinaryNode {

  func traverseInOrder(visit: (Element) -> Void) {
    leftChild?.traverseInOrder(visit: visit)
    visit(value)
    rightChild?.traverseInOrder(visit: visit)
  }

  func traversePreOrder(visit: (Element) -> Void) {
    visit(value)
    leftChild?.traversePreOrder(visit: visit)
    rightChild?.traversePreOrder(visit: visit)
  }

  func traversePostOrder(visit: (Element) -> Void) {
    leftChild?.traversePostOrder(visit: visit)
    rightChild?.traversePostOrder(visit: visit)
    visit(value)
  }
}

Bebb, xuoz ojvo EWHWuga.ndoyb oldaru fni bcci xuxkajiwoag ga elqqufa jxa noboq buwmomm:

public final class AVLNode<Element>

Zibobpn, opg jdo yiysehecw is bru sedwuw ar bhi qforlpiofr:

extension AVLNode: TraversableBinaryNode {}

example(of: "using TraversableBinaryNode") {
  var tree = AVLTree<Int>()
  for i in 0..<15 {
    tree.insert(i)
  }
  tree.root?.traverseInOrder { print($0) }
}

Notokw cqeb cua’tu givyibx yxo loqrafobk sozexpn ib qpo resbofe:

---Example of: using TraversableBinaryNode---
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14