First Time Learning Non-Linear Data Structures
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.