In [2]:

    

class BinaryTreeNode:

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

    def insert_left(self, value):
        self.left = BinaryTreeNode(value)
        return self.left

    def insert_right(self, value):
        self.right = BinaryTreeNode(value)
        return self.right


    

In [24]:

    

def is_superbalanced(tree):
    parents = [tree]
    children = []
    shallowest_leaf = None
    depth = 0
    
    while len(parents) > 0:
        depth += 1
        
        for parent in parents:       
            if parent.left is not None:
                children.append(parent.left)

            if parent.right is not None:
                children.append(parent.right)

            # if is leaf
            if parent.left is None and parent.right is None:
                if shallowest_leaf is None:
                    print 'found leaf at depth %s' % (depth)
                    shallowest_leaf = depth
                if shallowest_leaf is not None and depth - shallowest_leaf > 1:
                    print 'exiting at depth %s because its too far from leaf found at %s ' % (depth, shallowest_leaf)
                    return False

        # let the children grow to be loving parents
        parents = children
        children = []
        
    return True


    

In [25]:

    

tree = BinaryTreeNode(0)

is_superbalanced(tree)


    

    




found leaf at depth 1






    
Out[25]:





True

In [26]:

    

tree.left = BinaryTreeNode(1)

is_superbalanced(tree)


    

    




found leaf at depth 2






    
Out[26]:





True

In [27]:

    

tree.right = BinaryTreeNode(1)

is_superbalanced(tree)


    

    




found leaf at depth 2






    
Out[27]:





True

In [28]:

    

tree.right.left = BinaryTreeNode(2)

is_superbalanced(tree)


    

    




found leaf at depth 2






    
Out[28]:





True

In [29]:

    

tree.right.right = BinaryTreeNode(2)

is_superbalanced(tree)


    

    




found leaf at depth 2






    
Out[29]:





True

In [30]:

    

tree.right.left.right = BinaryTreeNode(3)

is_superbalanced(tree)


    

    




found leaf at depth 2
exiting at depth 4 because its too far from leaf found at 2 






    
Out[30]:





False

In [ ]: