Monday, April 25, 2016

max width (or widths) of binary tree

Use backtracking. Used here.
width(n):
    if n == null:
        return 0
    leftwidth, rightwidth = widths(n, 0)
    return -leftwidth + 1 + rightwidth

widths(n, offset = 0):
    if n == null:
        return 0, 0
    lw_l, rw_l = widths(n.left, offset -1)
    lw_r, rw_r = widths(n.right, offset +1)
    leftwidth = min(lw_l, lw_r, offset)  // min of left widths, offset
    rightwidth = max(rw_l, rw_r, offset) // max of right widths, offset
    return leftwidth, rightwidth

No comments:

Post a Comment