A road named NoNameUno

A refresher -

A binary tree is a kind of tree, that can have only two subtrees. So it will have left subtree, and a right subtree. This is going to be our first topic in this series...

The use of it became important, mainly due to dynamic sturctures that needed for searching, among other operations like:Add, Delete etc. If we keep records (aka structure or objects ) in a linear fashion, then given a key ( which is nothing but an ID of a record), we need to find if it exists or not. If it does, return it or delete it or move up to the root etc. The operations depends on what we want to do with it.

We can see that if we use keys to make the tree in a sorted order, then assuming the best case, we can search for an item in the tree in O(logN), since the max height of the tree is O(logN) when fairly balenced. This is when BST (binary search tree) comes handy.

From the search and / or other operational perspective, there are 3 fundamental tree traversals: In order; Preorder; and PostOrder. Two fundamental assumption here is that a node has two children. When we say Inorder, we mean to say - Operate on left child, then operate on the node, then operate on the right child. In data structure and algorithm books you will find them called visit, instead of operate on a node, but they are same. This is where the operations takes place.

Preorder traversal is - Operate on the node, then operate on the left node, then on the right node. Postorder is defined as - Operate on the left, then on the right, then on the node.

Note that, in a BST usually the keys are in non-decreasing sorted order. So if you traverse the nodes, in Inorder, you will have the sorted list of keys. Hence the name, InOrder.

BFS is breadth first order, so if you draw a simple BST and relate the search to preorder, you see that BFS is achieved. Where as, DFS is depth first and it is InOrder traversal technique.

DFS is inherently recursive, so it uses the underlying call stack, while BFS is inherently iterative, so it uses a queue to push and pop nodes to operate on in prescribed order.

Before we go into those traversals, and related problems that could be solved, of course using examples, we want to have some introduction to the analysis technique. Basic analysis of these are well laid out in many books. What is new here, is the online algorithm analysis. So ...

For now, take a look at a linked list. Single link following the next element, until it reaches a null node. When it is bit large, and we want to optimize the access pattern using some heuristics like: Move the recently accessed node to front, hope it would be accessed again soon, we get into a debate of how good is the approach!! If we know the offline sequence of access pattern, then analysis is different than when there is no pre determination of the sequence of operations. This is where Competitive cost analysis came to play. 

MTF(move to front) in a linked list was first under the radar of analysis when it was quite popular in some systems level programming, and a due analysis was required. AFAIK, this kicked off a new branch of analysis called - Compititive cost analysis. And it was started by Bob Tarjan and Dan Sleator, back in 80s.