Chapters

Hide chapters

Data Structures & Algorithms in Dart

First Edition · Flutter · Dart 2.15 · VS Code 1.63

Section VI: Challenge Solutions

Section 6: 20 chapters
Show chapters Hide chapters

8. Chapter 8 Solutions
Written by Kelvin Lau & 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? 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 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;
}

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