Assignment 1 [10 marks]
Deadline: Your lab in the week starting at 7 Dec 2024

This assignment is individual, each student must write his own code.
You are not allowed to copy any piece of code from the internet or from any other resource.
You are not allowed to copy any piece of code from other students.
You are allowed to make a partial implementation for a partial mark.

Implement a BTree data structure as described in our lecture with O(n) space and O(log n) Insert() and O(n) Print() operations.
Use only in standard C++, such that the following main() works. You are not allowed to modify the main().
Your code must be general and works for other data types and orders.
You can assume that the number of levels in the BTree will not exceed 50.
You are not allowed to include any files or built-in libraries, except for output.

int main()
{
    // Construct a BTree of order 3, which stores int data
    BTree<int,3> t1;

    t1.Insert(1);
    t1.Insert(5);
    t1.Insert(0);
    t1.Insert(4);
    t1.Insert(3);
    t1.Insert(2);

    t1.Print(); // Should output the following on the screen:

    /*
    1,4
      0
      2,3
      5
    */

    // Construct a BTree of order 5, which stores char data
    BTree<char,5> t;

    // Look at the example in our lecture:
    t.Insert('G');
    t.Insert('I');
    t.Insert('B');
    t.Insert('J');
    t.Insert('C');
    t.Insert('A');
    t.Insert('K');
    t.Insert('E');
    t.Insert('D');
    t.Insert('S');
    t.Insert('T');
    t.Insert('R');
    t.Insert('L');
    t.Insert('F');
    t.Insert('H');
    t.Insert('M');
    t.Insert('N');
    t.Insert('P');
    t.Insert('Q');

    t.Print(); // Should output the following on the screen:

    /*
    K
      C,G
        A,B
        D,E,F
        H,I,J
      N,R
        L,M
        P,Q
        S,T
    */

    return 0;
}