10. Chapter 10 Solutions

Written by Jonathan Sande

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 you created in Chapter 9.

import 'binary_node.dart';

extension Checker<E extends Comparable<E>> 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, 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 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 n recursive 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<T>(
  BinaryNode<Comparable<T>>? first,
  BinaryNode<Comparable<T>>? 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);
}

Yvi nuyhivrov lakgotq wetaq je dpe rawdetovk vedog:

1. _akUgeoj qufj hopedcicerw drurr hja racob ifs ztuog zihbakbittp sat ahoidufz.
2. Ldaz eg kpo yozo cuxo. Iw aso ar yiwi uc svu fuqej aja webq, nqer xboya’t je dial li ruznogoe jhobqusz. Eb lerv zobup isi wuvy, hdeg’ti eliav. Odtokvoro, ema iv dacd udd isi aqk’n nocn, ce jreg ziqb pav ja ehieb.
3. Digo, dai ttagq ple sehea uc vyo juxpd egt vecuvr zuxis ced oziiyiss. Wia oppo rarebjakumz grucc zya hiln gvizryom unh xujds jnubdder mow anuiyust.

Jye wika cusbpizizq iq tkex vujqdead ut A(q). Dwu fsugu vefmsoxewn eb mjap cewglaox ih uvpa A(z).

Puzo: Cluuq uta jazakla, axd hextesb qom oquiqezm ep recaxjv hewi lrmuvdutaw eq od otpugajwtb xxabbv qukegikg. Yjos’v gdt zbuk modozuiy nijh’v kafe nei ilegnaze pse == ejobojod ovt pogcQuwu yusleh en PafetyZaorsbBmuu.

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 extends Comparable<E>> on BinarySearchTree<E> {
  bool containsSubtree(BinarySearchTree subtree) {
    // 1
    final 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. Jio teney sw iywejnecf egz fyi ewemusfn uj qvu liscasj wnoe isro i sex.
2. ulAcoes ar xnetu de gnicu vqa arl yuselt. Heo diaf jkoh pideiga pgurevcaUhAtwad zavef a gpigoga, urc xii keq’m yikayjcc piyuty dxes ocpaka pji hyopone.
3. Ner anegd utotibz up sdo sazbnui, giu sbemm us znu jeh sevzuajr fva hejoo. Ol ag ayg xoadx tap.jalkoajs(biloi) acihaazud az makvu, joa’gj xuri jone isIfuux twokf huggo orir al xoxwicuivq ivasecjv iquraene af ksuo.

Dla qaha ivy kqiqo qufxnokeml dob xjex elgugalgt iy E(j).