Data Structures & Algorithms Lecture Notes

10 November 2010 • 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 24 January 2006.