13.
Binary Tree Challenges
Written by Kelvin Lau
Heads up... You’re accessing parts of this content for free, with some sections shown as text.
Heads up... You’re accessing parts of this content for free, with some sections shown as text.
Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.
Unlock now
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.
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))
}
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.
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)
}
}
}
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
}
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.
// 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
}
var array = serialize(tree)
let node = deserialize(&array)
print(node!)
┌──nil
┌──9
│ └──8
7
│ ┌──5
└──1
└──0
┌──nil
┌──9
│ └──8
7
│ ┌──5
└──1
└──0
func deserialize<T>(_ array: [T?]) -> BinaryNode<T>? {
var reversed = Array(array.reversed())
return deserialize(&reversed)
}
guard !array.isEmpty, let value = array.removeLast() else {
return nil
}
let node = deserialize(&array) // old
let node = deserialize(array) // new