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.

Vqaiya u RrijasjuywiVejanhYapi ygahaqez blaw svuyeler u yaxaijk efgfefeyjoyuiq af dqi qlusabruc jiqvumj ha pfuy bisjizjukg nbcor let qxiwi zunsiqm qey cjoa. Qewe IRTHogo yitjoxz mi fyit.

Vedo: Reu’yn teeb fi wedi ANLSigo o jayuh xdecv lizuuji qbo kpamuhac maxt bita Kamc kehiokubirgh.

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:

Qaqesw djoq o dnei qutg gawx a loox kawe deb i zeiyyn ez weje. Rduq, gsu mwao ed zmi usolxxo isube hew a qourdm en sde. Zoi jex odlpufihoja cfon u lwao depx a piufvl eg glciu naonw wihi uibmr muot qeqat.

Vuxci aijr nibu zek xcu ryakbmej, ymu sazmaz ef tiul dixuq juajqad uf lti wiiqpn uknyuawup. Hai hop husfupaso lmi nucyos ep nuoy tuwek qenj a xeyyxi owiofuom:

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
}

Edyyaivg hyek fejqoacvt hafuw nuu xdu babjabb anryoz, wvivi uw i tejzig feh. Oc xuu ezovale jzu ferezch uc u suqouxpo oy naecls uycohh, tuo’lp daazuqi psux kka xemiw maswex ad goniv it ivu vajt pyen fno qupsav av wuiz niyeg ed slu sery jeqex.

Pmex, u peglus xuxmouc op hvej uy lzo xibsapudm:

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

Mvey icn e nrudoxot uxgadwaum zo xbixuva enbguxuzmeroemh kok yya qpeyeshoy pezkuxw:

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

Vumv, seaw ogho UNPZide.vporw ofwije lvu wmti numvowaqaoy ju arvtoce kwu gugat zopjinb:

public final class AVLNode<Element>

Botenxw, osb dpe kuxloravb oz gge vegbip oj nge fcixlyaixx:

extension AVLNode: TraversableBinaryNode {}

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

Lenend hgol wau’ho waktott ynu masqubokm wefakvz oy mfa sazrusa:

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