# 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 that I understand the statement "the idea that an entire structure is stored in one variable"... You mean that a pointer to the root is stored in one variable? Otherwise it would be like saying that my entire earnings history is stored in my Social Security Number. Yes? Do students know that a variable is just a memory location that holds something? That the something could be "the address of another memory location"? Yes? Without that knowledge, I wonder at how they would understand recursion or anything else in programming. Oct 5, 2020 at 0:14
• Yes they know what a variable really is, I didn't want to waste words. What I meant by that comment is that they struggle with accessing a data structure through one variable (memory location storing other memory locations). Their pointer skills are adequate for how long they've been practicing, recursion is a different story. Oct 5, 2020 at 15:47
• When I learned about linked data structures, I had the advantage (?) of having to hand in assignments written in a computer language that had neither pointer types, nor reference types. The links in my data structures were integer indices into statically allocated arrays of records. Learning how to use pointers later on was almost painless: It was easy to think of them as just integer indices into a big array called "memory." Oct 15, 2020 at 16:37

## 5 Answers

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 "work" 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 <- 0;
Fun recur x {
If x > 0 {
Print x; // winding phase
recur x - 1;
s <- 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 "bottom-up" 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 "deeper" 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 "paint" it. You can either "apply colors" before the recursion of "paint" or after, stopping at the innermost doll. You can talk about how messy your fingers get if you do all of the "apply colors" 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 "apply colors" 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 "inner" dolls instead of one for each intermediate doll.

• The Russian Doll image is very good, and even better the image of getting paint all over your fingers from trying to do the steps in the 'wrong' order. Coming up with the correct and elegant solution is extremely satisfying, and is what makes programming worthwhile. Oct 5, 2020 at 0:16
• This answer simply does not address the question. Your knowledge of LL(n) compiler semantics is not appropriate material for a high school class where the poor teacher has learners that 'find it hard to understand that a whole structure can be stored in one variable'. Nov 27, 2020 at 23:02
• @JonGuiton, actually, the point was that the OP needs to review structural induction and understand it deeply, not that they should teach a compiler course. And, I flagged it myself as a not-answer. It is only a path to find an answer. Nov 27, 2020 at 23:10
• Beg to differ, but first time learners in a high school where some students find the idea of compound variables tricky do not need to review structural induction any more than first time automotive maintenance students need to deeply understand hydrocarbon oxidation theory. It is much more helpful for teaching staff if answers address audience needs and contain practical teaching aids at the appropriate level e.g. examples actually written in C would be useful for a teacher teaching data-structures in C. Nov 27, 2020 at 23:30
• i.e. which do not use functional programming paradigms with global variables - what kind of example is that setting? Nov 27, 2020 at 23:32

I tried a hybrid of both your suggestions together @Buffy, @Rusi Beginning with induction principle leading to an inductive definition...for lists in haskell.

We began by proving that: $$\sum_{i=0}^n i = \frac{n(n+1)}{2}$$ as learnt in school. Then we dwelt a bit on the process and the structure of numbers and how induction indeed proves our claim. That the process of construction of numbers is (+1) and from here we took a leap to (x:xs) as the process of construction of lists

sum [] = 0
sum (x: xs) = x + magic
where
magic = sum xs


The magic was the induction hypothesis. And we did not simplify the code until this sunk in.

So I never once called it recursion, always induction.

Its been magical! week3 into intro course and the kids are pumping out all kinds of recursive definitions. And now they use the words synonymously!

• There seems to be a spurious backquote (‛) in your sum definition. And yes, @buffy suggestion toward structural induction is spot on. I meant to say that but we ended up somewheres...else
– Rusi
Sep 27, 2020 at 17:32
• spurious backquote fixed Sep 27, 2020 at 17:38
• And thanks for reminding me that the beauty of Tex math works on this site — my answer changed accordingly. Seemingly irrelevant but actually germane to the point that recursion becomes easy to the extent that programming becomes math
– Rusi
Sep 28, 2020 at 4:31
• I have to ask how this is an answer to the question about teaching tree data structures in a high school. Nov 27, 2020 at 23:06
• A senior CMU Prof makes a similar point: existentialtype.wordpress.com/2011/04/12/a-dead-dog and existentialtype.wordpress.com/2011/03/21/…
– Rusi
Feb 14, 2021 at 15:59

# Is Recursion hard?

Peter Deutsch, the creator of the smalltalk implementation that inspired the Java-jit (and much else), famously said:

To iterate is human, to recurse divine

So you and your struggling students are in august company!

Now let's turn over to math. And not just math but...

# Basic school math

Here are two identities

\begin{aligned} a(b+c) &= ab + ac & \text{distributive law} \\ x^{m+n} &= x^m x^n & \text{index law} \end{aligned}

I guess everyone will agree that in the context of school math these are unproblematic? Almost trivial?

Lets special-case the above with $$c=1$$ in the first and $$n=1$$ in the second and we get \begin{aligned} a(b+1) &= ab + a \\ x^{m+1} &= xx^m \end{aligned}

Lets now ponder...

• Are these equations in any way difficult?
• Do you (anyone) find it an issue that they are recursive?
• Does one even notice that they are recursive?

(Assuming that the answer to all the above is no,no,no)
Lets ask now:
Whats this to do with programming?

Well... All we need are base cases, respectively $$a.0 = 0$$ $$x^0 = 1$$

And we get a complete recursive specification for multiplication as repeated addition and exponentiation as repeated multiplication

These can be trivially1 translated to haskell as

a*(b+1) = a*b + a
a*0     = 0


and

x^(m+1) = x*(x^m)
x^0     = 1


# Returning to the Programming world

Ok so you say that this is some math-toy. What's it to do with programming?

# An inappropriate pun

In almost all today's programming languages you can write the "statement" i = 1

And in math we write $$i = 1$$

Doing the first makes the second true; or staying in the programming world, after i = 1 i == 1 becomes true

So what's the big deal? Well programmers also write i = i+1

(Or moral equivalents like i++ i += 1 etc)

So after i = i+1 does i == i+1 ?!

Lets ask our math-respecting executor Haskell:
One can easily enough write

 i = i+1


And no trouble...it seems

But when we ask what is x we get, almost literally, an explosion!

 ? i

ERROR: Control stack overflow


In effect our executor is saying that it got into trouble trying to "solve the equation" $$i=i+1$$

# So is the problem in programming or math??

Mathematicians would almost universally protest at $$i=i+1$$ as

• wrong
• impossible
• no (finite) solution
• or just plain nonsense
• etc

Clearly if we programmers accept i=i+1 as normal and ok we cannot then expect our programs to respect mathematical concepts.

So it seems we have

# An inevitable dilemma: Programming XOR Mathematics

This seems like a very high price to pay!

But there's good news!

A large number of very intelligent people for many decades have thought about the problem and come to a very simple conclusion:

# The culprit is assignment

• Once you have assignment, a mathematical semantics of our programming language is a lost cause
• Throw the assignment out of the programming language (and morally equivalent things like mutating data-structures)2 and your programming language essentially becomes mathematics

# A bit of terminology

• Those who think as above and prefer assignment-free3 languages are typically called functional4 programmers
• Languages with assignment are called imperative languages (and from the pov above OO and classic imperative languages are much the same)

# Conclusion

So in answer to your explicit statement: My students find recursion hard! and its implied questions: Am I or my students doing something wrong?

The answer is Yes: Using imperative programming in a first programming course 5 befuddles their thinking

Or hear Dijkstra's take on this

1 Ok for those who try this in haskell there are some wrinkles -- Ive tested in gofer -- GOod For Equational Reasoning -- a Haskell predecessor which facilitates this kind of playing around better than Haskell

2 Mutation is actually much worse than assignment; in fact mutation messes up imperative programming as much as imperative programming messes up mathematics. A brief trailer

3 And sequencing... A story for another day

4 "Functional" is actually a misnomer; something like "mathematical" would have been better.

5 Imperative programming of course must be taught; if it is done in a later course, there is no unnecessary confusion.

• Why the insulting tone? Can you make your point otherwise? Note also that the language of instruction may not be up to the instructor or the OP here. Sep 27, 2020 at 15:20
• @buffy I changed the "you" to "I" in last para. (I actually don't understand all the versions!) Does that help? Or were you thinking of the other question cseducators.stackexchange.com/a/6567/8837
– Rusi
Sep 27, 2020 at 15:28
• Your comments about the teacher and the students in the "warning" section are not called for. Sep 27, 2020 at 15:33
• @buffy i think there's a communication problem here. I really mean the order is reversed (typically). And the innocent party — student or teacher — is punished for an inept medium of instruction. Anyways... I've made the order more explicit and toned down the epithets. Hope that helps!
– Rusi
Sep 27, 2020 at 15:44
• Do you teach? Do you think of your students as dumb? Sep 27, 2020 at 15:53

Weak recursion skills are, indeed, the big problem here. I also teach advanced high school students, and over the years, I have found that about 15% of students "get" recursion quite quickly, but I haven't found any shortcuts to getting the other 85% to mastery. Instead, we slog through, using a functional language (Racket) for about 8 weeks. By the end of that time, they are all quite good at recursion; the language demands it.

If I were limiting myself to an imperative language, then I would resign myself first and foremost to the idea that it simply takes time to absorb the norms of recursion. Unfortunately, eight weeks is about right. You can break it down as "base case first, then the recursive case" until you're blue in the face, but it will simply take time and a lot of practice for students who have already gotten quite good at thinking imperatively to be able to switch over to a paradigm so starkly different.

Perhaps have them start by building a linked list of ints, one method at a time. Let them try the given, then show them how to do it. Build append(int), then length(), then find(int), then insert(int, int), then, then, then... you can pick an order based on how you wish to present it all.

You could then follow this up by bringing them back to their very early programming assignments and ask them to redo the assignments, but ban for, while, and goto (assuming you ever let them use that -- yuck!). Tell them that the only way permissible to get a loop structure is to use function calls, and allow them to work in pairs without any sort of penalty if they get themselves right and truly stuck. This will get them used to the mechanics of recursion without having an attendant data structure to also have to learn about.

I'd avoid trees until they are able to build mildly complex programs using recursion, because the cognitive tax of recursion is too high to additionally make sense of the data structure (never mind self-balancing! With how long this all takes, you may decide to forgo that goal for now.)

If you do find any faster ways, please post a self-answer. The only approach I've found is to slog, slog, slog, slog. It takes time, but it works well, and everyone does eventually get quite good at it.

Good luck!

• People only understand something they have 'learned' after a night of sleep. I guess it takes about 40 days (and more importantly, 40 nights) to learn some things. That is just part of being human, no shortcuts available. Can't tell you how many times I stared dumbfounded at a programming problem one day, and the next morning sat down and polished it off. Naps should be required in programming. Having kids stop taking naps after Kindergarten is really a failure of the educational system. College is great because there is very flexible sleep time. Oct 5, 2020 at 0:24

I would probably go with expression trees.

2 + ( 6 * x * 3 )  --->

+
/   \
2    *
/  \
*  3
/ \
6   x


It demystifies something, it's based on pre-existing knowledge, there are umpteen ways to generate practical exercises and it represents an abstract use of the data type. It's also fun.

Moving on you could look at common sub-expressions as a way of introducing DAGs. The tree traversals have different applications also - e.g. postorder traversal is useful for evaluation.

Sorry, its not a pseudo academic answer oozing with self aggrandising polemic but it seems to fit the tone of your question. Worked well with my lot.