# 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.

## 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:

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)))
}
}
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)
}
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)
}
}
public final class AVLNode<Element>
extension AVLNode: TraversableBinaryNode {}

example(of: "using TraversableBinaryNode") {
var tree = AVLTree<Int>()
for i in 0..<15 {
tree.insert(i)
}
tree.root?.traverseInOrder { print(\$0) }
}
---Example of: using TraversableBinaryNode---
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.