[Trees and Graphs] interview questions #4

[rygh4775]

Check Balanced: Implement a function to check if a binary tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one.

[btakeya]

Use characteristics of BST: left < parent < right. Note that, every node that left child of some node A is smaller than A, similarly every node that right child of A is bigger than A.

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

    def __repr__(self):
        return "({} - {} - {})".format(self.left, self.value, self.right)

import sys

def validate(tree):
    queue = []

    node = tree
    queue.append((node, 1, sys.maxsize))

    is_invalid = False

    while len(queue) > 0:
        node_meta = (queue[0])
        node = node_meta[0]
        min_val = node_meta[1]
        max_val = node_meta[2]
        queue.remove(node_meta)

        if node.left is not None:
            if node.left.value >= node.value or node.left.value <= min_val or max_val <= node.left.value:
                is_invalid = True

            queue.append((node.left, min_val, node.value))

        if node.right is not None:
            if node.right.value <= node.value or node.right.value <= min_val or max_val <= node.right.value:
                is_invalid = True

            queue.append((node.right, node.value, max_val))

    return not is_invalid

if __name__ == '__main__':
    normal = Node(20, Node(10, Node(5, Node(3), Node(7)), Node(12)), Node(30, Node(22), Node(35, Node(32))))
    abnormal1 = Node(15, Node(17), Node(12))
    abnormal2 = Node(12, Node(10, Node(7), Node(15)), Node(15))
    abnormal3 = Node(10, Node(7, Node(2), Node(9)), Node(12, Node(5), Node(15)))

    print("*** normal")
    print(validate(normal))
    print("*** abnormal1")
    print(validate(abnormal1))
    print("*** abnormal2")
    print(validate(abnormal2))
    print("*** abnormal3")
    print(validate(abnormal3))

*** normal
True
*** abnormal1
False
*** abnormal2
False
*** abnormal3
False

[btakeya]

From root node, check if height of left child - height of right child > 1. If true at any node, tree is not balanced.

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

def get_height(node):
    if node is None:
        return None

    if node.left is not None:
        left_height = get_height(node.left)
        if left_height is None: return None # left subtree is not balanced
    else:
        left_height = 0

    if node.right is not None:
        right_height = get_height(node.right)
        if right_height is None: return None #right subtree is not balanced
    else:
        right_height = 0

    if abs(left_height - right_height) > 1:
        return None
    else:
        return max(left_height, right_height) + 1

def check_balanced(root):
    result = get_height(root)
    return True if result is not None else False

if __name__ == '__main__':
    balanced = Node(3, Node(5, Node(1), Node(7)), Node(4, Node(3)))
    print(check_balanced(balanced))
    unbalanced = Node(3, Node(9, None, Node(5, Node(6))), Node(10))
    print(check_balanced(unbalanced))