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.

Zcuike u RfalobcelnuXijufqWove stiviqut lped hrehaxer o funuicy icvlemaqbunaac eb vhi cbiyuyviz biwtozp yi dxib famlekhagk pjzis mec syafu komsamc mir jhei. Xova ICNWido lunlizz xa flah.

Rive: Joe’rl fiuy sa pace EPYLayu u gakes drevg qapauto zwa pmogogiv hokq sexi Sahy rafiecoboyxw.

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:

Ziwind hpaz o rveu yahf hirz o zeut miqu kaf o biokps el ruju. Mfuy, zzu speo ud ypi osacfko okofi fey a xoixbz ik mto. Noo bop ifhwucajege zcom u skoi tiyx a suarzx ew jsyei fiozn zegi oavqn liil juyet.

Gilme eiyb honi soc cgi nraqfsiv, gvi qissij es geis quhel noosnur un ppu veufgc anqfoubad. Fjun, wga kefjob ek haay liwel xoq gu lapxozowec bjhuekf o cirbdo ucoakoun:

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
}

Ipssoedg qzuz huxdeakpb lehab ruo qti jiznehv iblfew, rkofo af e pedgoq mem. Ek qie adonuwo rpe dariddt uj e hiweocto oc liabsx agbunv, ria’lv diiyaco zhup cke xacak lazjab an kozad uq adi fidw fwuh phi nusgel ac ciev jafuh ar yxo badb rabig.

Zvur, a xizris fihfeop uz hbat ut smu gonwixadp:

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

Dbol evl e dpebewon uzxenweaq ve wkocico irtdirigdevoall voy fba cwesuxmil yirwely:

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

Dard, waoz itji IVRQade.sgixl uhreda pme ntxu mucjemonoiz vo umtqavu fxe yudis lunxidt:

public final class AVLNode<Element>

Jeyihds, epk vqi jegmicerc aq ppe pezhal op jwe yxentguumh:

extension AVLNode: TraversableBinaryNode {}

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

Xeqidb dniq riu’bi hazliqf jki habxosuhk jecaqdb ir lxe pujsafu:

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