Chapters

Hide chapters

Data Structures & Algorithms in Swift

Third Edition · iOS 13 · Swift 5.1 · Xcode 11

Before You Begin

Section 0: 3 chapters
Show chapters Hide chapters

13. Binary Tree Challenges
Written by Kelvin Lau

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled 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 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.
© 2024 Kodeco Inc.

You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now