First Time Learning Non-Linear Data Structures I'm looking for effective strategies and projects for introducing non-linear data structures to students.  I currently teach linked lists, stacks, and then introduce binary trees.  A lot of students struggle with the idea that an entire structure is stored in one variable and is not in any particular order (other than infix, prefix etc).  The other thing I notice is weak recursion skills tend to spell doom when first trying to learn these data structures and their operations.  What are some ways for a struggling student to practice recursion in a meaningful way (projects or tools)?  What are some good accompanying algorithms for trees, and eventually self balancing binary trees?
The course focuses on C and is aimed at advanced high school students.
I'm not sure this qualifies as an actual answer, but let me suggest that you give yourself a course in Structural Induction. Perhaps you already know of this, of course. But the main idea is that the processing of a data structure (the method invocations) matches the structure of the data itself.
Thus, for a binary tree, a method processing an internal node (or the root) will make (recursive) calls to the two child nodes, with the recursion ending at a leaf. This is actually how a recursive descent compiler works, with the processing (parsing) exactly following the structure of the language as defined in a (LL) grammar.
One important lesson that you have to teach is that a recursion can do &quot;work&quot; both on the winding phase (before the recursive calls) or after (when they return). That is easily demonstrated with the following code (pseudocode) snippet:
Global s &lt;- 0;
Fun recur x {
    If x &gt; 0 {
        Print x; // winding phase
        recur x - 1;
        s &lt;- s + x;
        Print x; // unwinding phase
    } Else {
        Println;
    }
    return s;
}

Translate that to your favorite language and see what it outputs for a call like recur 10.
For a tree structure that means that you can recurse (twice) before you process the current node, thus having the results of the two recursions available. This is often called &quot;bottom-up&quot; processing. OR, you can work top-down by computing something in the current node and passing it down with the two recursive calls. Bottom-up processing can be used to construct a tree, for example as is often done in optimizing compilers.
As proof of a &quot;deeper&quot; understanding of recursion. Ask the students to write a linear running time function to copy a list. A quadratic function is easy, but linear running time is a bit harder.

To teach the winding v unwinding idea I often used a matryoshka. Imagine that you have an unpainted matryoshka (which I do), and you want to &quot;paint&quot; it. You can either &quot;apply colors&quot; before the recursion of &quot;paint&quot; or after, stopping at the innermost doll. You can talk about how messy your fingers get if you do all of the &quot;apply colors&quot; operations on the winding phase, since you have to open a freshly painted doll. A bit weirder, though it demonstrates the point, is that you can &quot;apply colors&quot; to one half on the winding phase and to the other half on the unwinding phase.
As a bridge from linear to tree-like structures, imagine a matryoshka that has two &quot;inner&quot; dolls instead of one for each intermediate doll.