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

9. Chapter 9 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.

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);
}

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;
  }
}
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