gistfile1.txt

//  Binary Tree 
	
// 	Given a binary tree, Print nodes of extreme corners of each level but in alternate order.

//     3
//    / \
//   9  20
//      /  \
//    15   7

// print 3 20 15
//  left most on the 0-th level
// right most on the 1-th level
// left most on the 2-th level. …..

3
3 -> queue
-> dequeue 
-> 3
  -> left right 9, 20 into the queue
-> find 20, not 9
-> dequeue 9, 
-> dequeue 20, put 15, 7 into queue
-> 
assume you have a queue, how will you determine which 

class TreeNode {
	TreeNode left;
	TreeNode right;
	int val;
}

keywords:

binary tree, 
extreme corners of each level:
 0-th left most
 1-th rigth most 20 pl
 2-th level -left most 15
alternate order:
 same meanings, alternate direction for each level, start from leftmost first
 
ask: print node in alternate order 

//     3
//    / \
//   9  20
//      /  \
//    15   7

//
// time complexity: O(n)
// space complexity: O(n)

public static IList<Node> PrintNodeExtremeCornerAlternateOrder(Node root) 
{
  var traversal = new List<Node>(); 
  
  if(root == null)
    return traversal; 
  
  var queue = new Queue<Node>(); 
  
  queue.Enqueue(root); // node3
  var leftMost = true; 
  
  while(queue.Count > 0) // true, true
  {
    var countLevelNode = queue.Count; // 1, 2
    
    for(int index = 0; index < countLevelNode; index++) // 9, 20
    {
      var visit = queue.Peek(); // node3
      
      if((leftMost && index == 0) || (!leftMost && index == countLevelNode - 1))
      {
        traversal.Add(visit);  //  node3       
      }                     
      
      queue.Dequeue(); 
      
      if(visit.left != null)
      {
        queue.Enqueue(visit.left);
      }
      
      if(visit.right != null)
      {
        queue.Enqueue(visit.right); 
      }
    }
    
    // outside the level orders - 
    //
    leftMost = leftMost? false : true; // false 
  }
  
  return traversal; 
}