Friday, March 20, 2015

if binary tree is balanced

BT is balanced when difference between depths (heights) of left and right subtree is <= 1.

// inefficient
depth(node):
    if node == null:
        return 0
    return 1 + max(depth(node.left), depth(node.right))

is-balanced-bt(node):
    if node == null:
        return true
    depthleft = depth(node.left)
    depthright = depth(node.right)
    if abs(depthleft - depthright) > 1:
        return false
    return is-balanced-bt(node.left) && is-balanced-bt(node.right)

A better way is to "bubble up" the depth. For a node, if the difference in depth for left and right is 1+ then return -1 instead. If depth for either left or right is -1 then bubble -1 up.
// efficient
depth(node):
    if node == null:
        return 0
    depthleft = depth(node.left)
    if depthleft == -1
        return -1
    depthright = depth(node.right)
    if depthright == -1
        return -1
    if abs(depthleft - depthright) > 1
        return -1
    return 1 + max(depthleft, depthright)

is-balanced-bt(node):
    return depth(node) != -1

No comments:

Post a Comment