Pasted

// Written by Claire Cavanaugh, 2016
 
 
    tlnode<T>* get_node(std::size_t n) {
        /* Gets the nth node of the tree or returns an error if 0 is
         * received as an argument. This was a bit of a weird thing to
         * write. Essentially, say you have a tree that looks like
         * this:            __________64(1)__________________ 
         *          ____28(2)_______                     ___53(3)____ 
         *     __13(4)___        ___19(5)__         43(6)            0(7)
         *   2(8)      1(9)   3(10)        XX(11)
         * 
         * Where the number in parenthasis is the index that node
         * would be if we were using a vector-based approach, OR the
         * number in the parentheses is the number assigned to the
         * node starting at 1 for the root and counting up, going left
         * right, top to bottom. I'll refer to that number as simply
         * the node number. 
         *
         * In the diagram our tree size is 10. Let's say we wanted to
         * add another value (bringing the total size up to 11). In
         * order to add a node at 11 (notated with XX's in the
         * diagram), we need the address of the parent of the
         * soon-to-be node (node 5, value of 19). Finding a path down
         * to this node seems rather tricky given just the number 5,
         * and at first this really confused me, but I figured out
         * (all by myself!! I'm proud of this) that when you convert a
         * node number to binary, you wind up with "directions" to the node.
         *
         * Let's try this out. The binary representation of 5 is
         * 101. The root node is always going to be a 1 in the number
         * because all binary numbers except zero start with 1
         * (discounting leading zeros). The 0 tells us to go to the
         * left child, then the 1 tells us to go to the left. If we
         * try this with 11, our representation is 1011, and as you
         * can see, following the "zero is left, one is right"
         * convention, 0 1 1 leads us to node 11. 
         * 
         * So this function uses recursion to cleverly convert to
         * binary in a way. We give it the node number we want, and it
         * says "okay, I'm node 11. 11 % 2 is 1 so whatever the path
         * to me is, it ends in 1, which makes me the right child of
         * my parent, but who is my parent?. My parent's node number
         * must be 11 / 2 = 5, so I'll call get_node(5) to find out
         * the address of my parent.". Get_node(5) deduces that it too
         * is the right child of it's parent (5 % 2 = 1), and that its
         * parent is node 2 (5 / 2), and so it requests the address of
         * its parent with get_node(2). get_node(2) sees that 2 % 2 is
         * 0, so it's the left child of it's parent, and goes to find
         * out who it's parent is with get_node(2 / 2),
         * i.e. get_node(1). And hey! We know where node number 1 is, that's
         * the root node! So we hand the root node over to
         * get_node(2), get_node(2) uses the knowledge to return
         * root->left to get_node(5), get_node(5) uses it to return
         * root->left->right to get_node(11), and get_node(11) finally
         * returns root->left->right->right to its caller.
         *
         * That is quite the journey. I think I had more fun writing
         * this one function than I did the rest of the project.
         */
        if (n == 0) {
            throw std::logic_error("Tried to get 0th node. Is the queue empty?");
        }
        if (n == 1) {
            return root;
        }
        tlnode<T>* my_parent = get_node(n / 2);
        if (n % 2 == 0) {
            return my_parent->left;
        }
        else {
            return my_parent->right;
        }
    }