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 null instead. If depth for either left or right is null then bubble null up.
// efficient
depth(node):
    if node == null:
        return 0
    depthleft = depth(node.left)
    if depthleft == null
        return null
    depthright = depth(node.right)
    if depthright == null
        return null
    if abs(depthleft - depthright) > 1
        return null
    return 1 + max(depthleft, depthright)

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

No comments:

Post a Comment