Data Structures and Algorithms Lecture Notes

23 March 2011 • Trees

---

"Non-trivial" in this case means significantly different in its recursive and non-recursive forms. A list can be defined recursively:

A list is either:

• empty or
• an element followed by a list.

However, the recursive and non-recursive (iterative) versions of lists are essentially the same. This is not the case for trees, where the recursive version of trees is significantly simpler than the non-recursive version.

---

This page last modified on 2006 January 24.