3 different way Tree Traversal

=========================================================================
Node class for tree

class Node{
    int data;
    Node left;
    Node right;
}

=========================================================================
Case 1: pre-order 

Recursive

public static void preOrderRecursive(Node root){
    if(root == null)
        return;
		
    System.out.print(root.data + " ");		
    preOrderRecursive(root.left);
    preOrderRecursive(root.right);
}

NON-Recursive

public static void preOrderIterative(Node root){
    if(root == null)
        return;
		
    Stack<Node> unvisited = new Stack<Node>();
    unvisited.push(root);
	
    while(!unvisited.isEmpty()){
        Node node = unvisited.pop();
			
        System.out.print(node.data + " ");
        if(node.right != null)
            unvisited.push(node.right);
        if(node.left != null)
            unvisited.push(node.left);
    }	
}

=========================================================================
Case 2: in-order 

Recursive

public static void inOrderRecursive(Node root){
    if(root == null)
        return;	
	
    inOrderRecursive(root.left);
    System.out.print(root.data + " ");
    inOrderRecursive(root.right);
}

NON-Recursive

public static void inOrderIterative(Node root){
    if(root == null)
        return;
		
    Stack<Node> unvisited = new Stack<Node>();
		
    while(!unvisited.isEmpty() || root != null){
        if(root != null){
            unvisited.push(root);
            root = root.left;
        }else{
            root = unvisited.pop();
            System.out.print(root.data + " ");
            root = root.right;
        }
    }
}

========================================================================= 
Case 3: post-order 

Recursive

public static void postOrderRecursive(Node root){
    if(root == null)
        return;
		
    postOrderRecursive(root.left);
    postOrderRecursive(root.right);
    System.out.print(root.data + " ");		
}

NON-Recursive

public static void postOrderIterative(Node root){
    if(root == null)
        return;
		
    Stack<Node> finalStack = new Stack<Node>();
    Stack<Node> tempStack = new Stack<Node>();
	
    tempStack.push(root);
    while(!tempStack.isEmpty()){
        Node node = tempStack.pop();
        finalStack.push(node);
        if(node.left != null)
            tempStack.push(node.left);
				
        if(node.right != null)
            tempStack.push(node.right);
    }
	
    while(!finalStack.isEmpty()){
        Node node = finalStack.pop();
        System.out.print(node.data + " ");	
    }
}

Find a missing integer in an array of number

Find a missing integer in an array of number

Case 1: Sorted
Use two pointers to store previous and current value, and difference between two number should equal to 1.

public static int findMissing_Sorted(int[] input){
    if(input.length == 0)
        return 0;

    int prev = input[0];
    for(int i = 1 ; i < input.length ; i++){
        int curr = input[i];
        if((curr - prev) != 1)
            return (prev + 1);
        else
            prev = curr;
    }
    return 0;
}

Case 2: Unsorted
Get the sum of 1 to N, use formula sum = (N+1)*(N)/2
Minus the element in the array, and the remaining value is the missing number.

public static int findMissing_Unsorted(int[] input){
    if(input.length == 0)
        return 0;
   
    int N = 10;
    int max = (N + 1) * N / 2;
  
    for(int i = 0 ; i < input.length ; i++)
        max -= input[i];
   
    return max;
}

How to use *args and **kwargs in Python

from
http://www.saltycrane.com/blog/2008/01/how-to-use-args-and-kwargs-in-python/

http://docs.python.org/tutorial/controlflow.html#keyword-arguments

def test_var_args(farg, *args):
    print "formal arg:",farg
    for arg in args:
        print  "another arg:",arg
  


def test_var_kwargs(farg, **kwargs):
    print "formal arg:",farg
    for key in kwargs:
        print "another keyword arg: %s: %s" % (key, kwargs[key])

test_var_args(1, "two", 3, "four")
print '-'*40
test_var_kwargs(farg = 1, myarg2 = "two", myarg3 = 3, myarg4 = "four")

def test_var_args_call(arg1, arg2, arg3):
    print "arg1:", arg1
    print "arg2:", arg2
    print "arg3:", arg3

args = ("two", 3)
test_var_args_call(1, *args)

def test_var_args_call(arg1, arg2, arg3):
    print "arg1:", arg1
    print "arg2:", arg2
    print "arg3:", arg3

kwargs = {"arg3": 3, "arg2": "two"}
test_var_args_call(1, **kwargs)

Grid Walk

Challenge Description
There is a monkey which can walk around on a planar grid. The monkey can move one space at a time left, right, up or down. That is, from (x, y) the monkey can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Points where the sum of the digits of the absolute value of the x coordinate plus the sum of the digits of the absolute value of the y coordinate are lesser than or equal to 19 are accessible to the monkey. For example, the point (59, 79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 19. Another example: the point (-5, -7) is accessible because abs(-5) + abs(-7) = 5 + 7 = 12, which is less than 19. How many points can the monkey access if it starts at (0, 0), including (0, 0) itself?

InputThere is no input for this program.

Output
Print out the how many points can the monkey access. (The number should be printed as an integer whole number eg.
if the answer is 10 (its not !!), print out 10, not 10.0 or 10.00 etc)

exist = []
point = {}

#make sure the sum of digit is less or equal than 19
def belowUpper(x, y):
    if x<0 or y<0:
        return False
    abs_x = str(abs(x))
    abs_y = str(abs(y))
    sum_x = 0
    sum_y = 0
    for c in abs_x:
        sum_x = sum_x + int(c)
    for c in abs_y:
        sum_y = sum_y + int(c)

    if sum_x + sum_y <= 19:
        return True



#check the point is valid or not
def addToList(x, y):
    if belowUpper(x+1, y):
        tmp = str(x+1) + " " + str(y)
        try:
            point[tmp]
        except:
            point[tmp] = 1
            exist.append([x+1, y])
        
        
    if belowUpper(x, y+1):
        tmp = str(x) + " " + str(y+1)
        try:
            point[tmp]
        except:
            point[tmp] = 1
            exist.append([x, y+1])




#remove overlap part when x = 0 or y = 0
def removeOverlap(x, y):
    total = 0
    xx = x
    yy = y
    while True:
        if belowUpper(xx, yy):
           total += 1
           xx += 1
        else:
            break

    return total
    

#main function
exist.append([0,0])

start = 0

while True:
    addToList(exist[start][0],exist[start][1])
    start+=1
    if start >= len(exist):
        break

over = removeOverlap(0, 0)

print (len(exist) - (over)) * 4 + 1