[to understand the context of this problem, you should read the class #08 exercise sheet]

[AED053] Is this an AVL Tree?

In this problem you should only submit a binarySearchTree.h file with a self-containing definition of a class BSTree<T>

Base Code

Use as a basis the class BSTree<T> (see code | download code) which implements a generic binary search tree that was explained in classes, with methods to insert and remove values, to check if a value exists, to write a preorder traversal with N for the null nodes, and to compute the number of nodes and the height of the tree.

The Problem

Add a new method bool isAVL() const to the class. The method does not change the tree, so it should be const (as seen in the lectures). The function should return true if the search tree is an AVL tree and false otherwise. Recall that the tree is an AVL tree if it is a search tree and for all its nodes the (absolute) difference between the heights of the right and left branches is at most 1.

You can be assured that the tree is a binary search tree, because it will be built using successive calls to the insert method.

Submission

You should submit the file binarySearchTree.h with the method isAVL added to BSTree<T> as requested (and without removing any of the other existing methods). You can however create additional methods, if you need them.

Mooshak will use the following code to link to your class, read the inputs, build the trees and call your method, printing its result.

#include <iostream>
#include <string>

#include "binarySearchTree.h"

int main() {
  BSTree<int> t;

  // Read tree by inserting numbers
  int n;
  std::cin >> n;
  for (int i=0; i<n; i++) {
    int x;
    std::cin >> x;
    t.insert(x);
  }

  // Call method to check if tree is an AVL Tree
  std::cout << "t.isAVL() = " << (t.isAVL()?"true":"false") << std::endl;
  
  return 0;
}

8
42 25 56 21 45 64 15 61

t.isAVL() = false

Explanation of Example Input 1

The tree of the example input 1 corresponds to the following figure:

8
42 21 56 15 25 45 64 61

t.isAVL() = true

Explanation of Example Input 2

The tree of the example input 2 corresponds to the following figure: