EXERCISES 24.04

        static bool isLeaf<T>(BinNode<T> bt)
        {
            return bt.HasRight() && bt.HasLeft();
        }

        public static string WordInMaze(BinNode<char> bt)
        {
            char val = bt.GetValue();

            if (val == '!')
                return null;

            if (isLeaf(bt))
                return val.ToString();

            string valRight = WordInMaze(bt.GetRight());
            string valLeft = WordInMaze(bt.GetLeft());

            if (valRight == null && valLeft == null)
                return null;

            if (valRight != null)
                return val.ToString() + valRight;

            if (valLeft != null)
                return val.ToString() + valLeft;

            return val.ToString();
        }

        // pass a binary tree and a reference to the index
        public static T GetValueAt<T>(BinNode<T> bt, ref int index)
        {
            if (bt == null)
                return default(T);

            T x;

            // try getting the value from the left sub-tree
            x = GetValueAt(bt.GetLeft(), ref index);
            if (index < 0)
                return x;

            // try getting the value from this tree
            if (index == 0)
            {
                index--;
                return bt.GetValue();
            }

            index--;

            // try getting the value from the right tree
            x = GetValueAt(bt.GetRight(), ref index);
            if (index < 0)
                return x;

            return default(T);
        }