10 Chapter 10 Solutions¶

Solution to Challenge 1¶

A perfectly balanced tree is a tree where all the leaves are in the same level, and that level is completely filled:

1551412201724

Recall that a tree with just a root node has a height of zero. Thus, the tree in the example above has a height of two. You can extrapolate that a tree with a height of three would have eight leaf nodes.

Since each node has two children, the number of leaf nodes doubles as the height increases. You can calculate the number of leaf nodes with a simple equation:

int leafNodes(int height) {
  return math.pow(2, height).toInt();
}

Solution to Challenge 2¶

Since the tree is perfectly balanced, the number of nodes in a perfectly balanced tree of height 3 can be expressed by the following:

int nodes(int height) {
  int nodes = 0;
  for (int h = 0; h <= height; h++) {
    nodes += math.pow(2, h).toInt();
  }
  return nodes;
}

Although this certainly gives you the correct answer of 15, there’s a faster way. If you examine the results of a sequence of height inputs, you’ll realize that the total number of nodes is one less than the number of leaf nodes of the next level.

Thus, a faster version of this is the following:

int nodes(int height) {
  return math.pow(2, height + 1).toInt() - 1;
}

Solution to Challenge 3¶

First, open avl_node.dart and add the following interface to the top of the file:

abstract class TraversableBinaryNode<T> {
  T get value;
  TraversableBinaryNode<T>? get leftChild;
  TraversableBinaryNode<T>? get rightChild;

  void traverseInOrder(void Function(T value) action) {
    leftChild?.traverseInOrder(action);
    action(value);
    rightChild?.traverseInOrder(action);
  }

  void traversePreOrder(void Function(T value) action) {
    action(value);
    leftChild?.traversePreOrder(action);
    rightChild?.traversePreOrder(action);
  }

  void traversePostOrder(void Function(T value) action) {
    leftChild?.traversePostOrder(action);
    rightChild?.traversePostOrder(action);
    action(value);
  }
}

Next, replace first few lines of AvlNode to include TraversableBinaryNode and the @override annotations:

class AvlNode<T> extends TraversableBinaryNode<T> {
  AvlNode(this.value);

  @override
  T value;

  @override
  AvlNode<T>? leftChild;

  @override
  AvlNode<T>? rightChild;

  // ...

You can also delete the traversal methods in AvlNode since they are already included in TraversableBinaryNode.

Finally, run the following to test it out:

import 'avl_tree.dart';

void main() {
  final tree = AvlTree<int>();
  for (var i = 0; i < 15; i++) {
    tree.insert(i);
  }
  tree.root?.traverseInOrder(print);
}

Verify that you’re getting the following results in the console: