13. Binary Tree Challenges

Written by Kelvin Lau

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.

An example of serialization is JSON. Your task is to devise a way to serialize a binary tree into an array, and a way to deserialize the array back into the same binary tree.

To clarify this problem, consider the following binary tree:

A particular algorithm may output the serialization as [15, 10, 5, nil, nil, 12, nil, nil, 25, 17, nil, nil, nil]. The deserialization process should transform the array back into the same binary tree. Note that there are many ways to perform serialization. You may choose any way you wish.

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))
}

1. This is the base case for the recursive solution. If the node is nil, you’ll return -1.
2. Here, you recursively call the height function. For every node you visit, you add one to the height of the highest child.

This algorithm has a time complexity of O(n) since you need to traverse through all the nodes. This algorithm incurs a space cost of O(n), since you need to make the same n recursive calls to the call stack.

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.

For this solution, you’ll explore how to solve this challenge by choosing the pre-order 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)
    }
  }
}

This is the pre-order traversal function. As the code suggests, pre-order traversal will traverse each node and visit the node before traversing the children.

It’s important to point out that you’ll need to also visit the nil nodes since it’s important to record those for serialization and deserialization.

As with all traversal functions, this algorithm goes through every element of the tree once, so it has a time complexity of O(n).

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
}

serialize will return a new array containing the values of the tree in pre-order.

The time complexity of the serialization step is O(n). Since you’re creating a new array, this also incurs a O(n) space cost.

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.

Your goal is to iterate through the array and reassemble the tree in pre-order format. Write the following at the bottom of your playground page:

// 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
}

Here’s how the code works:

1. The deserialize function takes an inout array of values. This is important because you’ll be able to make mutations to the array in each recursive step and allow future recursive calls to see the changes.

2. This is the base case. If removeFirst returns nil, there are no more elements in the array, thus you’ll end recursion here.

3. You reassemble the tree by creating a node from the current value, and recursively calling deserialize to assign nodes to the left and right children. Notice this is very similar to the pre-order traversal, except you are building nodes rather than extracting their values.

Your algorithm is now ready for testing! Write the following at the bottom of your playground:

var array = serialize(tree)
let node = deserialize(&array)
print(node!)

You should see the following in your console:

  ┌──nil
┌──9
│ └──8
7
│ ┌──5
└──1
  └──0

  ┌──nil
┌──9
│ └──8
7
│ ┌──5
└──1
  └──0

Your deserialized tree mirrors the sample tree in the provided playground. This is the behavior you want.

However, as alluded earlier, the time complexity of this function isn’t desirable. Since you’re calling removeFirst as many times as there are elements in the array, this algorithm has a O(n²) time complexity. There’s a easy way to remedy that.

Write the following function just after the deserialize function you created earlier:

func deserialize<T>(_ array: [T?]) -> BinaryNode<T>? {
  var reversed = Array(array.reversed())
  return deserialize(&reversed)
}

This is a helper function that first reverses the array before calling the main deserialize function. In the other deserialize function, find the removeFirst function call and change it to the following:

guard !array.isEmpty, let value = array.removeLast() else {
  return nil
}

This tiny change has a big effect on performance. removeFirst is an O(n) operation, because after every removal, every element after the removed element must shift left to take up the missing space. In contrast, removeLast is an O(1) operation.

Finally, find and update the call site of deserialize to use the new helper function that reverses the array:

let node = deserialize(&array) // old

let node = deserialize(array) // new

You should see the exact same tree before and after the deserialization process. The time complexity for this solution is now O(n). Because you’ve created a new reversed array and chose a recursive solution, this algorithm has a space complexity of O(n).