def main():
    root = Node(0)
    root.set_right(10)
    root.right.set_right(20)
    root.right.set_left(5)
    root.set_left(-10)
    print get_common_ancestor(root.right.right, root.right.left)

	def make_tree(self):
		"""
		Constructs the tree by iterating nodesList.
		"""
		while self.nodesList:
			row = self.nodesList.pop(0)
			nodeId = self.idFn(row)
			#print 'make_tree,row is %s, node id is %s'%(row,nodeId)
			
			try:
				node = self.rootNode.get_child_by_id(nodeId)
			except:
				node = None
			
			if not node:
				node = Node(nodeId)
				node.data = row
				#print 'make_tree,created a new node, id is ',node.id
				parentId = self.pidFn(row)	
					
				# creates it's parent node and recursivelly creates the ancestor nodes of this node.
				self.parent(parentId, node)
				
				#print '****make_tree is end, maked branch is ******\n',self.rootNode
				#print 70*'-'
		
		return

def p_formalDecl(p):
    '''formalDecl : typeSpecifier IDENTIFIER
                  | typeSpecifier IDENTIFIER LBRACKET RBRACKET'''
    varName = p[2]
    varType = p[1].children[0].type
    for item in global_scope:
        if item[1] == varName:
            if item[0] == varType:
                print "Warning : Shadowing global variable %s near line %s.\n"  % (varName, p.lexer.lineno)
                
    match = False
    for item in local_scope:
        if item[1] == varName: #same identifier
            if item[0] == varType: #same type
                print "Syntax Error: Redefinition of local variable %s with type %s near line %s.\n" % \
                      (varName, varType, p.lexer.lineno)
            else:
                print "Syntax Error: Redefinition of local variable %s with type %s (originally type %s) near line %s.\n" % \
                      (varName, varType, item[0], p.lexer.lineno)
            global syntaxerrs
            syntaxerrs += 1
            match = True
                
    if not match:
        if DEBUG:
            print "New local variable %s %s declared near line %s.\n" % (varType, varName, p.lexer.lineno)
            
        if len(p) > 3:
            local_scope.append((varType, varName, "array"))
        else:
            local_scope.append((varType, varName))
            
    p[0] = Node("formalDecl", p[1:])
    if len(p) > 3:
        p[0].subtype = 'array'

 def testAll(self):
   if IGNORE_TEST:
     return
   node = Node(NAME)
   self.assertEqual(node.getName(), NAME)
   node.setName(NAME2)
   self.assertEqual(node.getName(), NAME2)

def find_solution_rec_DFS(node, solution, visited, limit):
    if limit > 0:
        visited.append(node)
        if node.get_data() == solution:
            return node
        else:
            # expand children nodes (cities with connection)
            node_data = node.get_data();
            children_list = []
            for a_child in connections[node_data]:
                child = Node(a_child)
                if not child.on_list(visited):
                    children_list.append(child)

            node.set_children(children_list)

            for child_node in node.get_children():
                if not child_node.get_data() in visited:
                    # recursive call
                    sol = find_solution_rec_DFS(child_node, solution, \
                                                visited, limit-1)
                    if sol != None:
                        return sol

        return None

def find_solution_BFS(connections, initial_state, solution):
    solved = False
    visited_nodes = []
    frontier_nodes = []
    startNode = Node(initial_state)
    frontier_nodes.append(startNode)
    while(not solved) and len(frontier_nodes) != 0:
        node = frontier_nodes[0]
        # extract node and add it to visited_nodes
        visited_nodes.append(frontier_nodes.pop(0));
        if node.get_data() == solution:
            # solution found
            solved = True
            return node
        else:
            # expand child nodes (cities with connection)
            node_data = node.get_data();
            children_list = []
            for one_child in connections[node_data]:
                child = Node(one_child)
                children_list.append(child)
                if not child.on_list(visited_nodes) \
                   and not child.on_list(frontier_nodes):
                    frontier_nodes.append(child)

            node.set_children(children_list)

def main():
    root = Node(0)
    root.left = Node(-10)
    root.left.left = Node(-20)
    root.left.right = Node(-5)
    root.right = Node(10)
    root.right.right = Node(20)
    print get_tree_median(root)

def main():
    root = Node(0)
    root.left = Node(-10)
    root.left.left = Node(-20)
    root.left.right = Node(-5)
    root.left.left.right = Node(-15)
    root.right = Node(10)
    print lca(root, -15, -5)

def main():
    root = Node(0)
    root.left = Node(1)
    root.left.left = Node(2)
    root.right = Node(1)
    root.right.right = Node(2)
    root.right.right.right = Node(3)
    root.right.left = Node(2)
    print is_balanced(root)

def main():
    root = Node(0)
    root.right = Node(1)
    print is_binary_search_tree(root, -float("inf"), float("inf"))
    root = Node(0)
    root.right = Node(2)
    root.right.left = Node(1)
    root.right.right = Node(1)
    print is_binary_search_tree(root, -float("inf"), float("inf"))

 def setUp(self):
     # create test objects
     self.n = Node('node1')
     self.n2 = Node('node2', '2')
     self.n3 = Node('node3', '3')
     self.n4 = Node('node4', '4')
     self.n5 = Node('node5', '5')
     self.n6 = Node('node6', '6')
     self.n7 = Node('node7', '7')

def createMinTree(low,high):
	if(low>high):
		return
	mid = (low + high)/2
	data = treeElements[mid]
	node = Node(data)
	node.left = createMinTree(low,mid-1)
	node.right = createMinTree(mid+1,high)
	return node

def main():
    root = Node(0)
    root.left = Node(1)
    root.right = Node(2)
    root.left.left = Node(3)
    root.left.right = Node(4)
    root.right.left = Node(5)
    root.right.right = Node(6)
    for i in range(7):
        print bfs(root, i), "\n"

def main():
    root = Node(1)
    root.set_left(1)
    root.left.set_left(2)
    root.left.set_right(1)
    root.set_right(2)
    root.right.set_left(1)
    root.right.set_right(1)
    root.right.left.set_left(2)
    count = [0]
    count_all_sums(root, count, 2)
    print count

def build_tree(lst):
    if lst == []:
        return
    middle = len(lst) / 2
    left_list = lst[:middle]
    right_list = []
    if len(lst) > 1:
        right_list = lst[middle + 1:]
    node = Node(lst[middle])
    node.left = build_tree(left_list)
    node.right = build_tree(right_list)
    return node

	def make_node(self,nodeId):
		"""
		Filters the row from self.nodesList by nodeId,
		and create a new Node.
		After node's creation,the row will be removed from the nodesList.
		"""
		row = filter( lambda i: self.idFn(i)==nodeId , self.nodesList)[0]
		#print 'make_node,row is %s, node id is %s'%(row,nodeId)
		node = Node(nodeId)
		node.data = row
		self.nodesList.remove(row)		
		return node

	def __init__(self, tier, start_time, end_time, data):
		'''
	 	@param tier: The Tier object representing the tier the entry is on.
	 	@param start_time: The start time of the entry.
	 	@param end_time: The end time of the entry.
	 	@param data: The annotation data the entry represents.
	 	'''
		TimeSeriesData.__init__(self, start_time, end_time)
		Node.__init__(self, tier)
		self._data = data
		
		# Pre-cache the member hash
		self.__hash = self.__calculate_hash()

def parse_ontology(inp):
    """
    Read the ontology and return it as a tree where labels are categories.
    """
    root = Node()
    root.label = 'root'
    # We add an empty first line so that lineno can start at 1, and therefore
    # match the actual line number in the file, which is 1-indexed.
    lines = [''] + inp.readlines()
    lineno = parse_ontology_level(lines, 1, 0, root)
    if lineno != len(lines):
        raise ValueError("line {}: underindented".format(lineno))
    return root

    def test_default_cted_node_is_empty(self):
        node = Node()

        self.assertFalse(node.cycle_check)
        self.assertTrue(node._parent is None)
        self.assertEqual([], node._children)

        self.assertTrue(node.parent is None)
        self.assertTrue(node.is_root())
        self.assertTrue(node.is_leaf())
        self.assertFalse(node)

        self.assertEqual(0, len(node))
        self.assertEqual(0, descendants_len(node))

    def testParent(self):
        head = Node(None, None)
        self.assertTrue(head.Parent is None)
        self.assertTrue(head.Left is None)
        self.assertTrue(head.Right is None)
        self.assertTrue(head.depth == 0)
        self.assertTrue(head.is_left is None)

        head.feature = 0
        head.threshold = 1.0
        self.assertTrue(head.feature == 0)
        self.assertTrue(head.threshold == 1.0)
        self.assertTrue(head._feature == 0)
        self.assertTrue(head._threshold == 1.0)