algo note

People often say “tree” when they mean “binary tree.”
People often say “tree” when they mean “binary search tree.”
Note one caveat to saying that lookup is O(log(n)) in a BST. Lookup is only O(log(n)) if you can guarantee that the number of nodes remaining to be searched will be halved or nearly halved on each iteration. In the worst case, each node has only one child. In such a case, you have a linked list because each node points to only one other node. Lookup then becomes an O(n) operation just as in a linked list. The good news is that there are ways to guarantee that every node has approximately the same number of nodes on its left side as its right. A tree with approximately the same number of nodes on each side is called a balanced tree.
Of the methods to guarantee that every node has approximately the same number of nodes per side, the most common is called a red-black tree.
Deletion and insertion are O(log(n)) operations in binary search trees.
Binary search trees have other important properties. For example, it is possible to obtain the smallest element by following all the left children, and to obtain the largest element by following all the right children. The nodes can also be printed out, in order, in O(n) time. It is even possible, given a node, to find the next-highest node in O(log(n)) time.
Another common tree is a heap. Heaps are trees (usually binary trees) with a twist: Each child of a node has a value less than or equal to the node’s own value.
Consequently, the root node always has the largest value in the tree, which means that it’s possible to find the maximum value in constant time: Simply return the root value. Insertion and deletion are still O(log(n)), but lookup becomes O(n).
Breadth-First Search The time to find a node is O(n), so this type of search is best avoided for large trees. A BFS also uses a large amount of memory because it is necessary to track the child nodes for all nodes on a given level while searching that level.
Depth-First Search DFS has much lower memory requirements than BFS because it is not necessary to store all of the child pointers at each level. In addition, DFS has the advantage that it doesn’t examine any single level last (BFS examines the lowest level last).

Preorder traversal of a node performs the operation first on the node itself, then on its left descendants, and finally on its right descendants. In other words, a node is always visited before any of its children.

Inorder traversal performs the operation first on the node’s left descendants, then on the node itself, and finally on its right descendants. In other words, the left subtree is visited first, then the node itself, and then the node’s right subtree.

Postorder traversal performs the operation first on the node’s left descendants, then on the node’s right descendants, and finally on the node itself. In other words, all of a node’s children are visited before the node itself.

Graphs are more complicated than trees. Like trees, they consist of nodes with children. (A tree is actually a type of graph.) Unlike trees, a node can have multiple “parents,” possibly creating a loop (a cycle). In addition, the links between nodes, as opposed to the nodes themselves, may have values or weights.

A graph with one-way edges is called a directed graph. A graph with only two-way pointers is called an undirected graph.

A preorder traversal is easily coded using recursion:

void preorderTraversal( Node root ){
   if( root == null ) return;
   root.printValue();
   preorderTraversal( root.getLeft() );
   preorderTraversal( root.getRight() );
}

Note that inorder and postorder traversals are almost identical; all you vary is the order in which the node and subtrees are visited:

void inorderTraversal( Node root ){
   if( root == null ) return;
   inorderTraversal( root.getLeft() );
   root.printValue();
   inorderTraversal( root.getRight() );
}

void postorderTraversal( Node root ){
   if( root == null ) return;
   postorderTraversal( root.getLeft() );
   postorderTraversal( root.getRight() );
   root.printValue();
}
The running time is always O(n) for these traversals.
public class Node {
   private Node left;
   private Node right;
   private int  value;

   public Node( Node left, Node right, int value ){
       this.left = left;
       this.right = right;
       this.value = value;
   }

   public Node getLeft() { return left; }
   public Node getRight() { return right; }
   public int getValue() { return value; }
}

void preorderTraversal( Node root ){
   NodeStack stack = new NodeStack();
   stack.push( root );
   while( true ){
       Node curr = stack.pop();
       if( curr == null ) break;
       curr.printValue();
       Node n = curr.getRight();
       if( n != null ) stack.push( n );
       n = curr.getLeft();
       if( n != null ) stack.push( n );
   }
}

Node findLowestCommonAncestor( Node root, int value1,
                              int value2 ){
   while( root != null ){
       int value = root.getValue();
       if( value > value1 && value > value2 ){
           root = root.getLeft();
       } else if( value < value1 && value < value2 ){
           root = root.getRight();
       } else {
           return root;
       }
  }

  return null; // only if empty tree
}
Hash tables have worst-case lookup of O(n) but the average case is O(1).