Exploring Non-Linear structures may require backtracking.
-
Linear: need to know where we are
-
Non-Linear: need to know where we are and where we have been (Theseus and the Minotaur, Help from Ariadne)
-
Keep track of each choice we make
-
Go back to the decision point and explore the consequences of making a different choice
-
Eliminate the possible choices at each intersection one at a time until you solve the problem
Data Structures 2 emphasizes backtracking:
The major data structures we look at in Data Structures 1 don't typically use backtracking.
