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

[AED052] Node Balance

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 int balance(const T & val) 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 an integer containing the imbalance of the node containing the value val. The imbalance is expressed as the height of the right branch minus the height of the left branch. If the value val doesn't exist, the method should return zero.

You can be assured that there will be no repeated values in the tree.

Submission

You should submit the file binarySearchTree.h with the method balance 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);
  }

  // Read queries and print their result
  int q;
  std::cin >> q;
  for (int i=0; i<q; i++) {
    int x;
    std::cin >> x;
    std::cout << "t.balance(" << x << ") = " << t.balance(x) << std::endl;    
  }
  
  return 0;
}

8
42 25 56 21 45 64 15 61
4
42 25 56 88

t.balance(42) = 0
t.balance(25) = -2
t.balance(56) = 1
t.balance(88) = 0

Explanation of Example Input

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

• t.balance(42) = 0, since the left and right branches of the node with 42 have the same height (2)
• t.balance(25) = -2, since in the node with 25 the right branch is empty (height -1) and the left branch has height 1, and -1 - 1 = -2.
• t.balance(56) = 1, since in the node with 56 the right branch has height 1 and the left branch has height 0, and 1 - 0 = 1.
• t.balance(88) = 0, since the value 88 is not in the tree.