9.
Chapter 9 Solutions
Written by Jonathan Sande
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
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<int>? node) {
// 1
if (node == null) return -1;
// 2
return 1 +
max(
height(node.leftChild),
height(node.rightChild),
);
}
- This is the base case for the recursive solution. If the node is
null, you’ll return-1. - Here, you recursively call the
heightfunction. 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.
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);
}
}
}
Serialization
For serialization, you simply traverse the tree and store the values into a list. The list elements 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;
}
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.
// 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;
}
final tree = createBinaryTree();
final list = serialize(tree);
final newTree = deserialize(list);
print(newTree);
┌── null
┌──25
│ └── 17
15
│ ┌── 12
└──10
└── 5
BinaryNode<T>? deserializeHelper<T>(List<T?> list) {
return deserialize(list.reversed.toList());
}
final value = list.removeLast();
final tree = createBinaryTree();
final list = serialize(tree);
final newTree = deserializeHelper(list);