9 Chapter 9 Solutions

Solution to Challenge 1

A binary search tree is a tree where every left child is less than its parent, and every right child is greater than or equal to its parent.

An algorithm that verifies whether a tree is a binary search tree involves going through all the nodes and checking for this property.

Write the following in your project. You’ll need access to the BinaryNode class that you created in Chapter 8.

import 'binary_node.dart';

extension Checker<E extends Comparable<dynamic>> on BinaryNode<E> {
  bool isBinarySearchTree() {
    return _isBST(this, min: null, max: null);
  }

  bool _isBST(BinaryNode<E>? tree, {E? min, E? max}) {
    // 1
    if (tree == null) return true;

    // 2
    if (min != null && tree.value.compareTo(min) < 0) {
      return false;
    } else if (max != null && tree.value.compareTo(max) >= 0) {
      return false;
    }

    // 3
    return _isBST(tree.leftChild, min: min, max: tree.value) &&
        _isBST(tree.rightChild, min: tree.value, max: max);
  }
}

isBinarySearchTree is the method that you’ll expose for external use. Meanwhile, the magic happens in _isBST, which is responsible for recursively traversing through the tree and checking that the BST rules are followed. It needs to keep track of progress via a reference to a BinaryNode, and also keep track of the min and max values to verify the BST rules. Here are the details:

1. This is the base case. If tree is null, then there are no nodes to inspect. A null node is a binary search tree, so you’ll return true in that case.
2. This is essentially a bounds check. If the current value exceeds the bounds of min and max, the current node violates binary search tree rules.
3. This statement contains the recursive calls. When traversing through the left children, the current value is passed in as the max value. This is because any nodes on the left side cannot be greater than the parent. Conversely, when traversing to the right, the min value is updated to the current value. Any nodes on the right side must be greater than or equal to the parent. If any of the recursive calls evaluate false, the false value will propagate back to the top.

The time complexity of this solution is O(n) since you need to traverse through the entire tree once. There is also an O(n) space cost since you’re making nrecursive calls.

Solution to Challenge 2

Testing equality is relatively straightforward. For two binary trees to be equal, both trees must have the same elements in the same order. Here’s what the solution looks like:

bool treesEqual(BinarySearchTree first, BinarySearchTree second) {
  return _isEqual(first.root, second.root);
}

// 1
bool _isEqual(BinaryNode? first, BinaryNode? second) {
  // 2
  if (first == null || second == null) {
    return first == null && second == null;
  }
  // 3
  return first.value == second.value &&
      _isEqual(first.leftChild, second.leftChild) &&
      _isEqual(first.rightChild, second.rightChild);
}

The commented numbers refer to the following notes:

1. _isEqual will recursively check two nodes and their descendants for equality.
2. This is the base case. If one or more of the nodes are null, then there’s no need to continue checking. If both nodes are null, they’re equal. Otherwise, one is null and one isn’t null, so they must not be equal.
3. Here, you check the value of the first and second nodes for equality. You also recursively check the left children and right children for equality.

The time complexity of this function is O(n). The space complexity of this function is also O(n).

Note

Trees are mutable and testing for equality on mutably data structures is an inherently tricky business. That’s why this solution didn’t have you override the == operator and hashCode method on BinarySearchTree.

Solution to Challenge 3

Your goal is to create a method that checks if the current tree contains all the elements of another tree. In other words, the values in the current tree must be a superset of the values of the other tree. Here’s what the solution looks like:

extension Subtree<E> on BinarySearchTree {
  bool containsSubtree(BinarySearchTree subtree) {
    // 1
    Set set = <E>{};
    root?.traverseInOrder((value) {
      set.add(value);
    });

    // 2
    var isEqual = true;

    // 3
    subtree.root?.traverseInOrder((value) {
      isEqual = isEqual && set.contains(value);
    });
    return isEqual;
  }
}

1. You begin by inserting all the elements of the current tree into a set.
2. isEqual is there to store the end result. You need this because traverseInOrder takes a closure, and you can’t directly return from inside the closure.
3. For every element in the subtree, you check if the set contains the value. If at any point set.contains(value) evaluates as false, you’ll make sure isEqual stays false even if subsequent elements evaluate as true.

The time and space complexity for this algorithm is O(n).