I heart trees

I've been taking a class on the fundamentals of data analysis and algorithms. Yesterday afternoon we talked about two methods of traversing a set of nodes and edges on a graph. Four hours ago (I can be slow sometimes) I had an epiphany that recursion is not the only method of finding a given item in a tree full of items.

For any given tree, one can search through all the given nodes recursively (a depth first traversal), or instead of that, one can search all nodes in successive levels (a breadth first traversal).

So let’s say I have a very complicated ASP.NET page that dynamically populates all kinds of simple and complex controls depending on the context of the situation. If I want to find a textbox with a certain ID that appears one quarter of the time and is not buried deep inside the control tree of the page, I am probably far better off with a breadth first traversal. Chances are I do not want to look inside of any complex web controls that may or may not be on the page for my textbox.

Also, I spent two hours today pondering asymptotic notation while sunning myself on the lawn by the social sciences building. That's joy.