import random

class XmasTree():
    def __init__(self,value=None,left=None,right=None):
        self.value=value
        self.left=left
        self.right=right

def print_tree(tree,level=0,sep=''):
    if tree == None: return
    print_tree(tree.right,level+1,".--")
    print '  '*(level-1)+sep+str(tree.value)
    print_tree(tree.left,level+1,"'--")

def build_tree(decorations, size = 5):
    def build_tree_helper(decorations, counter):
        if counter < size:
            node = XmasTree(random.choice(decorations), build_tree_helper(decorations, counter+1), build_tree_helper(decorations, counter+1))
            return node
    return build_tree_helper(decorations, 0)

def is_xmas_tree(tree):
    if tree==None:
        return True
    if abs(n_nodes(tree.left)-n_nodes(tree.right))>1:
        return False
    return is_xmas_tree(tree.left) + is_xmas_tree(tree.right)

def n_nodes(tree):
    if tree == None:
        return 0
    return n_nodes(tree.left) + n_nodes(tree.right) + 1