8 Chapter 8 Solutions

You can use the following code to create a demo tree for both challenges:

//  ┌──25
//  │ └──17
// 15
//  │ ┌──12
//  └──10
//    └──5
BinaryNode<int> createBinaryTree() {
  final n15 = BinaryNode(15);
  final n10 = BinaryNode(10);
  final n5 = BinaryNode(5);
  final n12 = BinaryNode(12);
  final n25 = BinaryNode(25);
  final n17 = BinaryNode(17);

  n15.leftChild = n10;
  n10.leftChild = n5;
  n10.rightChild = n12;
  n15.rightChild = n25;
  n25.leftChild = n17;

  return n15;
}

Solution to Challenge 1

A recursive approach for finding the height of a binary tree doesn’t take much code:

import 'dart:math';

int height(BinaryNode? node) {
  // 1
  if (node == null) return -1;

  // 2
  return 1 +
      max(
        height(node.leftChild),
        height(node.rightChild),
      );
}

1. This is the base case for the recursive solution. If the node is null, 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 and deserialize a binary tree. Your first task when encountering this question is to decide on the traversal strategy.

This solution will use the pre-order traversal strategy.

Traversal

Define the following extension in your project:

extension Serializable<T> on BinaryNode<T> {
  void traversePreOrderWithNull(void Function(T? value) action) {
    action(value);
    if (leftChild == null) {
      action(null);
    } else {
      leftChild!.traversePreOrderWithNull(action);
    }
    if (rightChild == null) {
      action(null);
    } else {
      rightChild!.traversePreOrderWithNull(action);
    }
  }
}

This function implements pre-order traversal. However, it differs from the traversePreOrder function that you wrote when going through the chapter because this one performs action even when the children are null. It’s essential to record those for serialization and deserialization.

As with all traversal functions, this algorithm goes through every node in 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 a list. The elements of the list have type T? since you need to keep track of the null nodes. Write the following function to perform the serialization:

List<T?> serialize<T>(BinaryNode<T> node) {
  final list = <T?>[];
  node.traversePreOrderWithNull((value) => list.add(value));
  return list;
}

serialize will return a new list 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 list, this also incurs an O(n) space cost.

Deserialization

In the serialization process, you performed a pre-order traversal and assembled the values into a list. The deserialization process is to take each value of the list and reassemble it back into a tree.

Your goal is to iterate through the list and reassemble the tree in pre-order format. Add the following function to your project:

// 1
BinaryNode<T>? deserialize<T>(List<T?> list) {
  // 2
  if (list.isEmpty) return null;
  final value = list.removeAt(0);
  if (value == null) return null;
  // 3
  final node = BinaryNode<T>(value);
  node.leftChild = deserialize(list);
  node.rightChild = deserialize(list);
  return node;
}

Here’s how the code works:

1. deserialize takes a mutable list of values. This is important because you’ll be able to make mutations to the list in each recursive step and allow future recursive calls to see the changes.
2. This is the base case. If the list is empty you’ll end recursion here. You also won’t bother making any nodes for null values in the list.
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 build nodes rather than extract their values.

Your algorithm is now ready for testing! Write the following in main:

final tree = createBinaryTree();
final list = serialize(tree);
final newTree = deserialize(list);
print(newTree);

You should see the result below in your console:

 ┌── null
┌──25
│ └── 17
15
│ ┌── 12
└──10
 └── 5

Your deserialized tree mirrors the original one. This is the behavior you want.

However, the time complexity of this function isn’t desirable. Since you’re calling removeAt(0) as many times as elements in the list, this algorithm has an O(n²) time complexity. Fortunately, there’s an easy way to remedy that.

Write the following function just after deserialize:

BinaryNode<T>? deserializeHelper<T>(List<T?> list) {
  return deserialize(list.reversed.toList());
}

This is a helper function that first reverses the list before calling the main deserialize function. In deserialize, find the removeAt(0) function call and change it to the following:

final value = list.removeLast();

This tiny change has a big effect on performance. removeAt(0) 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 list:

final tree = createBinaryTree();
final list = serialize(tree);
final newTree = deserializeHelper(list);

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