In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of November 30th
(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 #07 exercise sheet]

[AED034] Tree Paths

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

Base Code

Use as a basis the class BTree<T> (see code | download code) which implements a generic binary tree that was explained in classes, with methods to read a tree from standard input, to write several node traversals, to count the number of nodes, to compute the height and to see if it contains a certain value.

The Problem

Add a new method T & path(std::string s) to the class. The function should return a reference to the value stored in the path given by the string s.

The string s can be "_" (indicating the root of the tree) or it can be made up of 'L'(left) and 'R' (right) characters indicating the path to follow from the root to reach the desired node. It is guaranteed that the path is valid, i.e. that it corresponds to an existing node in the tree. The following figure shows 5 different paths in the same tree and which node is reached (the node in red with the number in white).

Submission

You should submit the file binaryTree.h with the method path added to binaryTree<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 "binaryTree.h"

// Read a tree of type t assuming "N" as the null value
// read n paths and call t.path() for each one of them
template <typename T>
void read() {
  BTree<T> t;
  t.read("N");

  int n;
  std::cin >> n;
  for (int i = 0; i<n; i++) {
    std::string s;
    std::cin >> s;
    std::cout << "t.path(\"" << s << "\") = " << t.path(s) << std::endl;
  }
}

int main() {

  std::string type;
  std::cin >> type;
  if (type == "int") read<int>();
  else if (type == "string") read<std::string>();
  
  return 0;
}

int
6 3 2 N N 5 N N 10 8 N N 25 N N
5
LR
L
RR
_
RL

t.path("LR") = 5
t.path("L") = 3
t.path("RR") = 25
t.path("_") = 6
t.path("RL") = 8

The example input corresponds to the tree and 5 paths of the example figure given in the problem description.