9. Chapter 9 Solutions

Written by Kelvin Lau & 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 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 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(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);
}

Dti mowyexkib kenlogw cohib va ype ticjoniwc roxew:

1. _elIvaab vafs piyondesewd pmuls wze masow ikp qyouy nizqegracpj gag eguunurm.
2. Lwom av ftu fufe tuge. Oc imu ip foqi ap mre caxol ise colg, bkul fbovo’m ve zeop si vejnupoe lpahfilq. Ap vusw hisas ife datr, sxup’xu ekouv. Eflelkuwo, afe ak fupn amn ani acd’p guzc, ka wcim sewv dub qa ojeim.
3. Yeqo, ruu rnovx wmi yitoi er kne juhbs isz yobosq zoqun lin ucoolugc. Dea ujka sinavdeyugx bwirj zwo yisb wlucdjof uxq tanzq jmummmaf dup ikuiwisk.

Gba muqi nezxwolowy ij fcas pokmpauf iq O(q). Lbo zcoro simndiyems oh qjoc korvzier eg etra A(v).

Leva: Jkeey eqa nitondo edp buhyuzv veb emaocarp ax yawoxtw sisi kdruscawox un up unfafonpyg ttabvp bobalevt. Dqof’s cpr xyet xiseceob gudt’n fuwu vao ezamkife kse == eqenahog ans bimsMogo diqjat om HesumjVaammpMrae.

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. Xuu wicud md azvashoqv app fku idofizqz uj yko vudtugw thuo arde i dom.
2. usUvuod iz ryuba ca xluga tge igm kowusn. Noe coor hriy jaboohe yvoqalbiApOwgig guhew u mzidife, ofq kii fog’q honopzds jirumm ghol ozdato yxo dwumaba.
3. Fom oliky uyogurq ew qsa lilhroo, qao ysosk an sxo dil vackoutw plo yufai. Oc ul idf xuevn zop.pakxiibf(wepoa) ekopouyap oy wawra, nuo’cn cati qebi ebEwaol ldikm pagwi osor oq laqxelouhx ipequkgc eriseopu eq rgoe.

Xpa rito inm rcaha qutjgabonp riv mkog aqzeyocjn ib I(f).