Chapters

Hide chapters

Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

Section VI: Challenge Solutions

Section 6: 21 chapters
Show chapters Hide chapters

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 scrambled 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),
      );
}
  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.

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);
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 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 Kodeco Personal Plan.

Unlock now