In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of December 7th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #08 exercise sheet]

[AED046] Is this an AVL Tree?

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

Base Code

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

The Problem

Add a new method bool isAVL() to the class. 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 tree is a binary search tree, because it will be built using sucessive calls to the insert method.

Submission

You should submit the file binarySearchTree.h with the method isAVL added to binarySearchTree<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: