Problem

Given a binary tree, write a function to determine whether the tree is balanced. A balanced binary tree is one in which the left and right subtrees of each node have heights that differ by no more than 1.
Example input:
Tree:
1
/ \
2 3
/ \
4 5
/
6
Output: True

Solution

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

def is_balanced(root):
    if root is None:
        return True
    left_height = get_height(root.left)
    right_height = get_height(root.right)
    if abs(left_height - right_height) > 1:
        return False
    return is_balanced(root.left) and is_balanced(root.right)

def get_height(root):
    if root is None:
        return 0
    return 1 + max(get_height(root.left), get_height(root.right))

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.left.left.left = Node(6)

print(is_balanced(root))