Home iOS & Swift Books Data Structures & Algorithms in Swift

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.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

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 height of the binary tree is determined by the distance between the root and the furthest leaf. 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 to be used 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: tree.leftChild), height(of: tree.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.

Have feedback to share about the online reading experience? If you have feedback about the UI, UX, highlighting, or other features of our online readers, you can send them to the design team with the form below:

© 2021 Razeware LLC

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 raywenderlich.com Professional subscription.

Unlock Now

To highlight or take notes, you’ll need to own this book in a subscription or purchased by itself.