Chapters

Hide chapters

Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

13. Binary Tree Challenges
Written by Kelvin Lau

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

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.

55 1 52 81 12 70

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
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.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now