Apr 092018Depth-first search (DFS) is a fundamental algorithm for working with trees, because it gives us a way to “visit” every node in the tree, once each.(1)
That’s important, because visiting every node is a subproblem of many other problems on trees.
DFS explores the full depth of one subtree before moving onto the next one.
If that’s the order we want to visit the nodes in, or the order doesn’t matter, then DFS is fine; otherwise, we need a different algorithm.
We’ll see one in this post.
Feb 122018A list can do everything an array can do, and more; the array data type is strictly “less useful” than the list data type.
However, the array data structure is both faster and uses less memory than any list data structure.(1)
This is common: if a data type supports fewer operations, then programmers who use that type have less freedom, but programmers who implement it (or choose an implementation) have more freedom.
A data structure supporting fewer operations can often be more efficient in speed, memory use, or both; or, if you want more operations supported, expect a lower efficiency.
